用C打印复合数的最大素数因子

我正在解决一个谜题，我需要找到用户输入的复合数字的最大素数因子。 我想到了一些东西，并尝试过，但它无法检测到复合数量因素中最大的素因子。

我在下面添加我的代码，如果有人能帮我在这里找到最大的素数，我将不胜感激。 在这些因素中打印出来。

// Accept a composite number from user and print its largest prime factor. #include 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=2; j 0) b = i; else if(i==3) b = 3; } } } printf("%d\nLargest prime factor: %d\n", c, b); } 

Answer 1

诀窍是，找到最小的素因子，并将复合数c除以它以获得最大的素因子。

诀窍是找到C / F为素数的最小因子F（从2开始）。 那么，C / F将是C的最大素因子。

编辑：看起来您还想列出所有因素。 问题是，在你测试素性的内部循环中，你为任何可以整除的数字设置了最大的素数。 换句话说，尝试这样的事情：

 is_prime = true; for (j = 2; j <= x / 2; j++) { if (i % j == 0) is_prime = false; } if (is_prime) largest_prime = x; 

请注意，您实际上可以比x除以2更早停止。您可以停在x的平方根处。 但是， 的sqrt()函数在您的情况下使用起来有点混乱，因为它适用于浮点数而不是整数。

Answer 2

要找到素数因子分解，通常可以找到2和sqrt（N）之间的所有因子。 您可以按每个因素划分复合，以获得其余因子。 然后递归以找出每个因素的主要因素。

完成后，您将获得所有主要因素的列表。 获取列表中最大的项目应该是相当微不足道的。

Answer 3

在你的内循环中，你设置b = i如果确实存在一个不是 i因子的数字。 如果不存在作为i因子的数字， 则需要设置b = i i 。

（“数字”，我的意思是“ 2和sqrt(i)之间的整数”当然）

Answer 4

因子分解是一个典型的数论问题。 您可以在数论教科书中找到许多分解算法。 其中一些可以在维基http://en.wikipedia.org/wiki/Integer_factorization上找到

Answer 5

嘿感谢输入的朋友，我做了一些事情，现在程序打印出复合数字的最大素数因子，只要复合数小于52，而对于高于此范围的更高范围，它不打印正确的输出。 我正在附加代码，请看看你们是否可以帮助我

 #include 

void main（）{int i，j，b = 2，c; printf（“\ n输入复合数：”）; scanf（“％d”，＆c）; printf（“因素：”）;

 for(i=1; i<=c/2; i++) { if(c%i==0) { printf("%d ", i); for(j=1; j<=i; j++) //since a numbr cand be divisible by a number greated than its half { if(i%j > 0) b = i; //b stores the largest prime factor 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); 

}

Answer 6

在Python中，像这样的东西会：

 import math import itertools # largest prime factor of a composite number def primality(num): for i in range(2,int(math.sqrt(num))+1): if num%i ==0: return 0 return 1 if __name__ == '__main__': number = 600851475143 for i in itertools.count(2,1): if number%i == 0: if number%10 in [7,9,1,3] and primality(number/i): print number/i break 

我所做的检查素性是整齐的平方根技术。