java查找10001:st素数（Euler项目）

Question

我正在做Euler项目的挑战7，它要求我找到10001:st素数

我的尝试如下：

    int i=2; //the number to check if prime
    int c=0; //the amount of prime numbers

    while(true){

        //checks if i%n == 0, if so, i is not a prime number. 
        for(int n=2;n<=prob.getMax(i);n++){
            //it is not a prime number
            if(i%n==0){
                break;
            }

            //it is a prime number 
            if(n==prob.getMax(i)){
                c++;
                break;
            }

        }
        i++;

        //if c == 10001 we have found the 10001:st prime number
        if(c==10001){
            System.out.println(i);
            break;
        }

    }

}

public int getMax(int x){

    return (int) Math.ceil(Math.sqrt(x));

}

返回的值为104760，但这似乎不正确。我无法理解我做错了什么，因为我似乎得到了一个合理的价值。谁能给我指一下正确的方向吗

还有：有没有更好的方法来计算这类问题？我似乎在使用for循环和brute强制方法来解决每个问题

Answer 1

在代码中，您没有检查for循环中的prob.getMax(i)。 在for循环的主体中添加另一个检查，如下所示：

if(n==theDesiredNumber){
 //...
 break;
}

Answer 2

在检查找到的素数是否为第10001个素数之前，先增加i。通过交换这些操作的顺序，它应该可以工作

Answer 3

在显示结果之前，您正在增加i（使用i++）。100001素数可能为104760-1

一个建议是，尽量避免这些（正确的）。您可以执行以下操作：

c = 0;
while (c < 10001) {
    ....
    c++
}

Answer 4

素数需要注意的一点是，除了数字2之外，它们都是奇数，你不必检查这个数字是否可以被它前面的每个数字整除

public class StackOverflow {
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // Starting at 1 cause I'm already including 2
        long primeCount = 1; 

        // Start with an odd number cause primes are never even
        long prime = 1;

        Calendar start = Calendar.getInstance();
        while (primeCount < 10001) {
            prime += 2;
            if (isPrime(prime)) {
                primeCount++;
            }
        }

        System.out.println(prime);
        System.out.println(String.format("Elapsed Time: %d ms", Calendar.getInstance().getTimeInMillis() - start.getTimeInMillis()));
    }

    private static boolean isPrime(long prime) {
        if (prime <= 1)
            return false;
        else if (prime % 2 == 0)
            return (prime == 2);
        else
        {
            int divisor = 3;
            double upperLimit = Math.sqrt((double)prime) + 1;

            while (divisor <= upperLimit)
            {
                if (prime % divisor == 0)
                    return false;

                // Skip by two cause an odd number is never evenly divisible by an even number
                divisor +=2;
            }
            return true;
        }
    }
}

结果（！！！！扰流板警报！！！！！）

Answer 5

通过搜索，您可以发现10001素数是104743。 我将您的算法更改为：

public static void main(String... args) {
  int i = 2; //the number to check if prime
  int c = 1; //the counter for prime numbers have found so far

    while (true) {

       if(isPrime(i)){
           c++;
       }

        //if c == 10001 we have found the 10001:st prime number
        if (c == 10001) {
            System.out.println(i);
            break;
        }
        i++;

    }

}

public static boolean isPrime(int number) {
    for (int i = 2; i <= getMax(number); i++) {
        if (number % i == 0)
            return false;
    }
    return true;
}

public static int getMax(int x) {

    return (int) Math.ceil(Math.sqrt(x));

}