素数因子算法：C， Python 例如：
陈莎拉
什么是质因数分解？
一个数的质因数是指它本身也是该数的因子。 素数只能被 1 和它本身整除。
计费示例： 10 的质因数是 2 和 5，因为 2 × 5 = 10。
使用迭代查找质因数
从 2 开始遍历到 sqrt(n)，并检查其是否能被整除。如果 n 能被当前候选数整除，则进行除法运算并输出结果。
计费示例： 大于 40 的每个质数都符合 n。2+n+41，所以 n = 0, 1, 2 得到 41, 43, 47。
如何打印一个数字的质因数？
- 遍历从 2 到 sqrt(n) 的数字。
- 检查 n 对每个候选数的模数；余数为零表示该候选数是质因数。
- 收集所有能整除 n 的质数。
- 该程序运行的时间复杂度为 O(sqrt(n))。
算法：
Set a counter i to 2 While i <= sqrt(n): While n % i == 0: n = n / i print i i = i + 1 if n > 1: print n
筛选算法
筛法存储每个数的最小质因数（在最大界限内），在预计算之后大幅降低因式分解的成本。
- 记录每个整数（不超过上限）的最小质因数。
- 取最小的质数并将其添加到因数集中。
- 用该质数除以该数，重复此过程直到结果为 1。
- 每个查询的运行时间约为 O(log n)。
计费示例： 除了 2 和 3 之外的素数符合 6n-1 或 6n+1 的形式。例如，5 = 6(1)-1 和 19 = 6(3)+1。
算法： 定义一个 排列 它存储每个数字的最小质因数，使用索引作为每个元素的初始值。
Set array[1] to 1 Set i to 2 While i*i <= max_number: If array[i] == i: Set j to i*i While j <= max_number: If array[j] == j: array[j] = i j = j + i i = i + 1 while the_number != 1: print array[the_number] the_number = the_number / array[the_number]
相关文章
Python 使用迭代法求质因数
下列 Python 代码使用迭代试除法寻找质因数：
import math def PrimeFactors(n): for i in range(2, int(math.sqrt(n)) + 1, 1): while n % i == 0: # find all the occurrences of a prime factor print((int)(i)) n = n // i if n != 1: # if the number was originally a prime print((int)(n)) n = (int)(input("Enter the number you want: ")) PrimeFactors(n)
输出：
Enter the number you want: 4 2 2
Python 使用递归计算质因数
此 Python 下面的代码使用筛法求给定数字的质因数。
import math High = (int)(1e5 + 7) array = [0 for i in range(High)] # generate smallest prime factors def Sieve(): for i in range(1, High): array[i] = i for i in range(2, math.ceil(math.sqrt(High))): if array[i] == i: for j in range(i * i, High, i): if array[j] == j: array[j] = i def PrimeFactors(n): # divide until we reach 1 if n == 1: return print((int)(array[n])) PrimeFactors((int)(n / array[n])) Sieve() n = (int)(input("Enter the number you want: ")) PrimeFactors(n)
输出：
Enter the number you want: 4 2 2
使用迭代的 C 素数因子程序
同样的迭代解决方案是用以下方式编写的： C输入一个数字，然后对于从 2 到 sqrt(n) 的每个候选数，检查其整除性并打印每个质因数的出现情况。
#include <stdio.h> int main() { int n; printf("Enter the number you want: "); scanf("%d", &n); for (int i = 2; i * i <= n; i++) { while (n % i == 0) // find all the occurrences of a prime factor { printf("%d\n", i); n /= i; } } if (n != 1) // if the number was originally a prime { printf("%d", n); } return 0; }
输出：
Enter the number you want: 2 2
使用递归的 C 素数因数程序
递归的 C 版本与此类似 Python 一：构建最小质因数数组，然后递归地用该质因数除以 n，直到 n 达到 1。
#include <stdio.h> int Max = 100007; int array[100007]; void Sieve() // smallest prime factors up to Max { for (int i = 1; i < Max; i++) array[i] = i; for (int i = 2; i * i <= Max; i++) { if (array[i] == i) { for (int j = i * i; j < Max; j += i) { if (array[j] == j) array[j] = i; } } } } void PrimeFactors(int n) { if (n == 1) // divide until we reach 1 return; printf("%d\n", array[n]); PrimeFactors(n / array[n]); } int main() { Sieve(); int n; printf("Enter the number you want: "); scanf("%d", &n); PrimeFactors(n); return 0; }
输出：
Enter the number you want: 2 2
关于质数的一些有趣事实
- 除 2 以外的任何偶数都可以写成两个质数之和（4 = 2 + 2，6 = 3 + 3，8 = 5 + 3）。
- 除了 2 和 3 之外，没有其他连续的质数，因为 2 是唯一的偶质数。
- 除了 2 和 3 之外的每个素数都符合 6n + 1 或 6n − 1 的形式，其中 n 为正整数。
- 一个数的质因数集合是唯一的。
- 数字 1 既不是质数也不是合数。
- 质因数分解有助于判断整除性、简化分数和寻找公分母。
- 质因数分解也是基于数字的密码学的基础。
