Python 质数判断、质数查找和质因数分解算法实现

import math

def is_prime(num): '判断一个数是否为质数' if num < 2: return False for i in range(2, int(math.sqrt(num))+1): if num % i == 0: return False return True

def find_primes(num): '找出小于等于num的所有质数' primes = [] for i in range(2, num+1): if is_prime(i): primes.append(i) return primes

def prime_factorization(num): '对一个数进行质因数分解' primes = find_primes(num) factors = [] for prime in primes: while num % prime == 0: factors.append(prime) num //= prime if num != 1: factors.append(num) return factors

if name == 'main': num = int(input('请输入一个整数：')) factors = prime_factorization(num) print('%d的质因数分解结果为：%s' % (num, factors))