Java中的素数 – 算法
我已经开始学习使用Java编写代码并决定使用Project Euler站点给我一些小任务来尝试完成我学习的每一段新编码。 所以我遇到了问题3 ：
13195的主要因素是5,7,13和29. 600851475143的最大主要因素是什么？
我想到了这个问题，并研究了很多关于素数的不同理论以及如何通过各种不同的计算找到它们（Sieve of Eratosthenes就是一个例子），我想到的解决方案是测试2 – > n中的数字并查看是否它们是素数，如果它们是那么我将把新发现的素数除以Tn变量（在这种情况下为600851475143）并查看它是否是一个因素。 如果是，我会将它分配给变量Hp（最高素数），在程序结束时我会将Hp输出到控制台以给出我的结果。
这是我的代码：
public class Largest_Prime_Factor_NEW_SOLUTION { static long Tn = 600851475143L; static long Hp = 0; static boolean isPrime = false; public static void main(String[] args) { for (long i=2; i<Tn; i++) { System.out.println("TESTING NUMBER " + i); for (long k=2; k < i; k++) { if (i % k == 0) { System.out.println(i + " IS NOT A PRIME"); break; } else if (k + 1 == i) { isPrime = true; } } if (isPrime) { System.out.println(i + " IS A PRIME"); if (Tn % i == 0) { System.out.println(Tn + " IS DIVISIBLE BY " + i); Hp = i; } else { System.out.println(Tn + " IS NOT DIVISIBLE BY " + i); } } isPrime = false; } System.out.println("THE HIGHEST PRIME NUMBER OF " + Tn + " IS " + Hp); } } 现在我知道这段代码非常低效，而且刚开始我已经设法从我开始的地方压缩它（到处都有循环！）但我要问的是，我该如何改进呢？ 它正在吞噬我，因为我所研究的一切都与其他人的做法相矛盾，而且非常令人困惑。 我已经尝试了筛选方法，但我知道布尔数组只能是一个int数组，而不是一个长数组？
我明白，当开始编码时，我将仅限于我可以使用的知识，但仅仅是出于兴趣，我很想知道最终的解决方案是什么。
你能做的就是找到Tn的最低除数。 假设是p ，再次找到Tn/p的最低除数，依此类推。
现在，每一步p都是素数[下面的解释]。 所以收集他们，他们是Tn的主要除数。
为了获得更好的时间复杂度，您可以仅检查高达ceil(sqrt(Tn))除数，而不是Tn-1 。
当你开始检查Tn主要除数时，你可以从2开始。 一旦你得到一个素数除数p不要再从2开始为Tn/p 。 因为， Tn/p也是Tn的除数，并且因为Tn没有小于p除数，所以Tn/p也没有。 所以再次从p开始[ p可以在Tn有多个功率]。 如果p不除Tn ，则移至p+1 。
示例：
Tn = 45
1.从2开始.2不分45。
2.下一个测试是针对3. 45可以被3整除。所以3是它的主要除数。
3.现在检查45/3 = 15的素数除数，但从3开始，而不是从2开始。 好吧，15可以被3整除。所以从15/3 = 5开始5.注意5，ceil（sqrt（5））是3.但是5不能被3整除。但是因为4> ceil（sqrt（ 5））我们可以毫无疑问地说5是素数。
所以45的主要除数是3和5。
为什么一个数字的最小除数（除了1）是素数？
假设上述陈述是错误的。 那么数字N具有最小但复合除数，比如说C.
所以C | N现在C是复合的，它的除数小于自身但大于1。
说这样的C除数是P.
所以P | C，但我们有C | N => P | N，其中1
这与我们的假设相矛盾，即C是N的最小除数，因此数字的最小除数总是素数。
感谢您的所有帮助，在阅读完评论和答案之后，我设法将代码进一步压缩到以下内容：
public class Largest_Prime_Factor_NEW_SOLUTION_2 { static long Tn = 600851475143L; public static void main(String[] args) { for (long i = 2; i < Math.sqrt(Tn); i++) { if(Tn % i == 0) { Tn = Tn / i; i--; } } System.out.println(Tn); } }
它完美无瑕！ 再次感谢您的帮助和时间来帮助我理解。 我知道这更像是一个数学问题，而不是一个编码问题，但它帮助我理解了一些事情。 我现在要去学习别的东西:)
既然你是在做这个学习练习，那么当你对当前的课程有所改进时，为什么不尝试以不同的方式解决同样的问题呢？ 费马分解方法首先找到大因子。
有很多方法可以改进像这样的程序，但改进主要是用数学而不是编程：
-
在寻找因素时，请检查每个数字，而不仅仅是素数。 如果你找到一个因素检查它是否是素数。 你可以通过这种方式省去许多素数检查。
-
复合数的最大素数因子最多可以是数字的平方根，因此您可以提前停止迭代。
-
使用快速素性测试而不是进行试验分割http://en.wikipedia.org/wiki/Primality_test
然后，这是一次性的。 不要过度复杂化。
通过试验分解对复合数进行分解的简单算法如下：
function factors(n) f, fs := 2, [] while f * f <= n while n % f == 0 fs.append(f) n := n / f f := f + 1 if n > 1 fs.append(n) return fs
该算法可以改进，并且有更好的算法来分析大数，但它足以完成您的任务。 当你准备好了更多的时候，我在我的博客上谦虚地推荐使用Prime Numbers编写的论文 ，其中包括该算法的实现以及Java中的其他算法。
这是这个的java版本：
static boolean isPrime(int n){ if (n == 2) return true; if (n == 3) return true; if (n % 2 == 0) return false; if (n % 3 == 0) return false; int i = 5; int w = 2; while (i * i <= n) { if(n % i == 0) return false; i += w; w = 6 - w; } return true; }
正如@Alexandru所描述的那样：它是经典O（sqrt（N））算法的变体。 它使用了这样一个事实：素数（除了2和3）的forms是6k-1和6k + 1，并且只看这种forms的除数。