素数因子算法:C, Python 例如:
什么是质因数分解?
给定一个素因数 任何 数字是 素数。因数相乘后得到另一个数。质数可以被自身或 1 整除。
换句话说,质因数是通过找出哪些质数相乘形成原始数字来确定的。
例如::10 的质因数是 2 和 5。这是因为 2X5 =10,并且 2,5、XNUMX 都是质数。
使用迭代查找质因数
要找到给定数字的质因数,我们首先遍历从 2 到该数字的平方根的所有数字,然后检查每个数字是否为质数。只要原始数字可以被这个质数整除,我们就在每次迭代中不断添加这个质数。
示例:
每个大于 40 的素数都写成以下公式:n2+n+41。因此,我们可以用所有数字代替 n 来找到相应的素因数。例如,02+0+41=41, 12+1+41=43, 22+2+41=47,…
如何打印一个数字的质因数?
- 在这种方法中,我们将对从 2 到该数字的平方根进行迭代,如上一节所述。
- 为此,我们需要检查从 2 到 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)) 时间复杂度内完成,大大提高了解决方案的效率。
- 这使得我们能够计算比使用以前的方法所能处理的更大数字的素因数。
示例:
第二种方法是检查数字是否可以写成 6n-1 或 6n+1,因为除 2 和 3 之外的任何质数都应该写在两个公式之一中。例如,5=6(1)-1、19=6(3)+1,......。
算法:
定义一个数组array,存储每个数的最小质因数,并以索引值作为数组每个元素的初始值 排列.
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 4
Python 使用递归计算质因数
本节展示了 Python language 使用筛选法找出给定数字的质因数。
import math High = (int)(1e5+7) array=[0 for i in range(High)] # function to generate all the smallest prime def Sieve(): #factors of the numbers until the maximum number 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): #We will keep dividing until we reach 1 if n == 1: return print((int)(array[n])) PrimeFactors((int)(n/array[n])) #Here we call the function after dividing it by this prime Sieve() n=(int)(input("Enter the number you want: ")) PrimeFactors(n)
输出:
Enter the number you want: 4 2 2
使用迭代的 C 素数因子程序
它与迭代 Python 的解决方案相同,但写成 C语言.
我们要求用户输入数字,然后对于从 2 到该数字的平方根的每个数字,我们需要通过打印该因数的所有出现次数来检查它是否可以被整除。
#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 素数因数程序
这与 Python 递归解决方案相同,但用 C 语言编写。
我们可以让用户输入数字;然后,我们构建 primes 数组,用于存储每个数字的最小素因数。最后,我们调用 Prime Factors 递归函数,该函数将给定数字除以其最小素因数,并重复执行,直到达到 1。
#include <stdio.h> int Max = 100007; int array[100007]; void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number { 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)//keep dividing until we reach 1 { return; } printf("%d\n",array[n]); PrimeFactors(n/array[n]);//call the function after dividing by //this prime } 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 之外的所有素数都可以写成以下形式:6 * n + 1 或 6 * n – 1,其中 n 是正整数。
- 一个数字的质因数集是唯一的。
- 数字 1 既不是质数也不是合数。
- 数字的质因数分解可以帮助解决可除性、简化分数以及寻找不同分数的共同分母等问题。
- 此外,质因数分解的其中一个令人兴奋的用途是破解基于数字的密码。