如何为Project Euler 7改进此代码？

通过列出前六个素数：2,3,5,7,11和13，我们可以看到第6个素数是13。

什么是10 001主数？

我的解决方案

public class Prime_Number { public static boolean isPrime(long n) { if ((n > 2 && n % 2 == 0) || (n > 3 && n % 3 == 0) || (n > 5 && n % 5 == 0) || n == 0 || n == 1) { return false; } return true; } public static void main(String[] args) { int count = 0; int prime = 0; while (prime <= 10001) { if (isPrime(count) == true) { prime++; if (prime == 10001) { System.out.println(count + " is a prime number" + "(" + prime + ")"); } } count++; } } } 

但它没有给出正确的答案。 请帮我升级我的代码。 例如，程序将91定义为素数，但它不是素数。 如何改进？

Answer 1

你需要测试每个素数小于其平方根的数字，以确保它是素数。

你只对2,3和5进行测试。

因为存储所有素数并不总是空间可行的，所以常见的技术是测试2，然后测试从3开始的所有奇数。这需要一个循环。

考虑：

 boolean isPrime(long n) { if (n < 2) return false; if (n == 2) return true; if (n % 2 == 0) return false; if (n < 9) return true; if (n % 3 == 0) return false; long max = (long)(Math.sqrt(n + 0.0)) + 1; for (int i = 5; i <= max; i += 6) { if (n % i == 0) return false; if (n % (i + 2) == 0) return false; } return true; } 

Answer 2

数字p是素数，如果它只分开它自己和1.你只检查3和5 divison。 这还不够。 检查每个数字直到p / 2 ，或更好直到sqrt(p) 。

Answer 3

以下解决方案仅检查奇数是素数，但它从头开始计为2作为素数：

 public class A { static int N = 10001; private static boolean isOddPrime(long x) { for ( int i = 3 ; i*i <= x ; i+=2 ) { if ( x % i == 0 ) { return false; } } return true; } public static void main(String[] args) throws Exception { long start = System.nanoTime(); int x; int i = 2; // 3 is the 2nd prime number for ( x = 3 ; ; x+=2 ) { if ( isOddPrime(x) ) { if ( i == N ) break; i++; } } System.out.println(x); long stop = System.nanoTime(); System.out.println("Time: " + (stop - start) / 1000000 + " ms"); } } 

输出 ：

 104743 Time: 61 ms 

Answer 4

我会评论，但我刚加入。

你不必检查1和数字平方根之间的每个数字是否有潜在的除数，你只需检查所有先前的素数（假设你从1开始并迭代），因为任何其他非素数的除数本身就是可以被较低值的素数整除。 素数越多，对非素数的检查就越多。 这个例子是在C＃中，但更多的是展示这个概念。

  //store found primes here, for checking subsequent primes private static List Primes; private static bool IsPrime(long number) { //no number will have a larger divisor withou some smaller divisor var maxPrime = Math.Sqrt(number); // takes the list of primes less than the square root and // checks to see if all of that list is not evenly // divisible into {number} var isPrime = Primes .TakeWhile(prime => !(prime > maxPrime)) .All(prime => number % prime != 0); if (isPrime) Primes.Add(number); return isPrime; } private static long GetNthPrime(int n) { //reset primes list to prevent persistence Primes = new List { 2, 3, 5, 7 }; //prime in starting set if (Primes.Count >= n) { return Primes[n - 1]; } //iterate by 6 to avoid all divisiors of 2 and 3 // (also have to check i + 2 for this to work) // similar to incrementing by 2 but skips every third increment // starting with the second, as that is divisible by 3 for (long i = 11; i < long.MaxValue; i += 6) { // only check count if is prime if ((IsPrime(i) && Primes.Count >= n) || (IsPrime(i + 2) && Primes.Count >= n)) { break; }; } //return end of list return Primes[n - 1]; }