大佬教程收集整理的这篇文章主要介绍了在c中查找复合数的最大素数因子,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
#include<stdio.h> void main() { int i,j,b=2,c; printf("\nEnter a composite number: "); scanf("%d",&c); printf("Factors: "); for(i=1; i<=c/2; i++) { if(c%i==0) { printf("%d ",i); for(j=1; j<=i; j++) { if(i%j > 0) { b = i; } if(b%3==0) b = 3; else if(b%2==0) b = 2; else if(b%5==0) b = 5; } } } printf("%d\nLargest prime factor: %d\n",c,b); }
提示#1:
如果除数是n的除数,则n /除数也是n的除数.例如,100/2 = 50,余数为0,所以2是100的除数.但这也意味着50是100的除数.
提示#2
给定提示#1,这意味着我们可以在检查素因子时从i = 2循环到i * i <= n.例如,如果我们检查数字100,那么我们只需要循环到10(10 * 10是<= 100),因为通过使用提示#1,我们将得到所有因子.那是:
100 / 2 = 50,so 2 and 50 are factors 100 / 5 = 20,so 5 and 20 are factors 100 / 10 = 10,so 10 is a factor
提示#3
由于我们只关心n的素因子,只需找到n的第一个因子,称之为除数,然后我们可以递归地找到n /除数的其他因子.我们可以使用sieve方法并在找到它们时标记因子.
bool factors[100000]; void getprimefactors(int n) { // 0 and 1 are not prime if (n == 0 || n == 1) return; // find smallest number >= 2 that is a divisor of n (it will be a prime number) int divisor = 0; for(int i = 2; i*i <= n; ++i) { if (n % i == 0) { divisor = i; break; } } if (divisor == 0) { // we didn't find a divisor,so n is prime factors[n] = true; return; } // we found a divisor factors[divisor] = true; getprimefactors(n / divisor); } int main() { memset(factors,false,sizeof factors); int f = 1234; getprimefactors(f); int largest; printf("prime factors for %d:\n",f); for(int i = 2; i <= f/2; ++i) { if (factors[i]) { printf("%d\n",i); largest = i; } } printf("largest prime factor is %d\n",largest); return 0; }
输出:
---------- Capture Output ---------- > "c:\windows\system32\cmd.exe" /c c:\temp\temp.exe prime factors for 1234: 2 617 largest prime factor is 617 > Terminated with exit @R_135_6756@.
以上是大佬教程为你收集整理的在c中查找复合数的最大素数因子全部内容,希望文章能够帮你解决在c中查找复合数的最大素数因子所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。