最大的质因数 java
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20812594/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Largest prime factor java
提问by tobgirado
I'm needing a little help with this:
我需要一点帮助：
public class BiggestPrimeFactor{
public static void main(String[] args){
long biggest=0L;
for(long i=2L; i<=600851475143L; i++){
if(600851475143L%i==0){
for(int l=1; l<=Math.sqrt(i); l++){
if (i%l==0){
break;
} else{
biggest=i;
}
}
}
}
System.out.println(biggest);
}
}//end of BiggestPrimeFactor
I don't know if it is okay or wrong, but it is taking way too much (more than half an hour then I got tired and closed command-line)...
我不知道它是好的还是错误的，但是它占用了太多的时间（超过半小时然后我累了并关闭了命令行）......
Can you help or at least tell me if it is fine?
你能帮忙，或者至少告诉我它是否好？
thanks!
谢谢！
i could solve it!!
我可以解决它！
this is what it does look like
这就是它的样子
public class BiggestPrimeFactor{
public static void main(String[] args){
long x=600851475143L;
long biggest=0L;
for(long i=2L; i<=x; i++){
for(long l=1L; l<=Math.sqrt(i); l++){
if(l%i==0){
break;
} else{
while(x%i==0){
x=x/i;
biggest =i;
}
}
}
}
System.out.println(biggest);
}
}//end of BiggestPrimeFactor
}//BiggestPrimeFactor 结束
and it took really little time! =P thanks for your help!
而且只用了很少的时间！=P 谢谢你的帮助！
回答by NPE
It seems that you are looking for the largest prime factor of 600851475143.
看来您正在寻找 600851475143 的最大质因数。
Once you have found a prime factor, you should repeatedly divide the target number by it. Only when you've done this should you proceed to checking further candidate factors. This will greatly reduce the amount of work your code has to do.
一旦你找到了一个质因数，你应该反复将目标数除以它。只有在您完成此操作后，您才能继续检查进一步的候选因素。这将大大减少您的代码必须完成的工作量。
For example, once you've established that 600851475143 is divisible by 71, replace 600851475143 with 600851475143 / 71 = 8462696833 and so on.
例如，一旦您确定 600851475143 可以被 71 整除，就将 600851475143 替换为 600851475143 / 71 = 8462696833 等等。
Additionally, once a factor is found in this manner, it will automatically be known to be prime. There will be no need for a separate primality test (HT @Henry for pointing this out).
此外，一旦以这种方式找到一个因子，它就会自动被称为素数。不需要单独的素性测试（HT @Henry 指出了这一点）。
Here is a pseudocode implementation of the algorithm in question:
这是所讨论算法的伪代码实现：
n = 600851475143
k = 2
m = None
while n > 1:
while n % k == 0:
m = k
n = n // k # integer division
k = k + 2 if k > 2 else 3 # 2, 3, 5, 7, 9, ...
print(m)
(This pseudocode happens to be valid Python and takes 35 milliseconds on my computer.)
（这个伪代码恰好是有效的 Python，在我的电脑上需要 35 毫秒。）
回答by theNinja
If you are going to call this method several times, you could optimize your search by building a list of primes. See Sieve of Eratosthenes:
如果您要多次调用此方法，您可以通过构建素数列表来优化您的搜索。见埃拉托色尼筛法：
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Then start with the smallest prime and work your way up and stop when you reach the square root of the number (if you haven't found a prime factor yet).
然后从最小的素数开始，一直向上，当你达到这个数的平方根时停止（如果你还没有找到一个素数）。
