找到第n个素数

Question

我不知道为什么当我输入某些 nthprime 数字时我的代码不起作用。我曾多次尝试更改我的代码，但每使一个 nthprime 工作，我就会让其他人的情况变得更糟。因此，如果我更改代码以使其适用于 nthprime=8，我会意识到 nthprime=7 而其他一些代码将停止工作。谁能指出我犯的一个具体缺陷，或者我应该重新考虑我的代码大纲。谢谢。

public class NthPrime {

public static void main(String[] args) {

    int nthprime;

    System.out.println("Enter value for n:");
    nthprime=IO.readInt();

    while(nthprime <= 0){
        System.out.println("Enter a positive value for n");
        nthprime=IO.readInt();
    }

    if(nthprime == 1){
        System.out.println("The nth prime number is: "+2);
    }
    if(nthprime == 2){
        System.out.println("The nth prime number is: "+3);
    }

    if(nthprime > 2){

    int prime=2; 
    int num=3;
    int square;
    boolean nonprime=false;

    while(prime < nthprime){
        prime++;
        num+=2;
        square = (int) Math.sqrt(num);
        for (int i=3; i <= square; i++){
            if (num % i == 0){
                nonprime=true;
                num+=2;
            }
            if(nonprime==false){
                prime++;
                num+=2;
            }
        }
    }
    System.out.println("The nth prime number is: "+num);
    }
}

}

Answer 1

检查这个循环：

for (int i=3; i <= square; i++){
        if (num % i == 0){
            num+=2;
        }
        else {
            prime++;
            num+=2;
        }
    }

您似乎想要循环所有奇数，直到您的数字的平方根。 如果其中之一相除，则应停止循环并将其标记为非素数。 如果它不整除任何数字，您应该将其标记为素数，但即使这样也应该在循环完成后完成。 （例如，当 i > 平方时）

我不想给你答案，因为你似乎想自己修复现有的循环。 但一种策略是将其标记为非素数（以布尔值形式），然后在循环之后检查布尔值，如果布尔值指示它是素数，则增加素数计数 (prime++)。 请记住重新初始化布尔值，以便下次遇到 for 循环时正确设置。

Answer 2

创建另一个方法来检查数字是否为素数，并使用 while 循环来获取素数。

public static void main(String[] args) {
    ...

    if (nthprime == 1) {
        System.out.println("The nth prime number is: 2");
    } else {
        int num = 3;

        for (int i = 2; i <= nthPrime; i++) {
            while(!isPrime(num)) {
                num += 2;
            }

            num += 2;
        }

        System.out.println("The nth prime number is: "+ (num - 2));
    }
}

private static boolean isPrime(int n) {
    int sqrt = (int) Math.sqrt(n);

    for (int i = 2; i <= sqrt; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

Answer 3

import java.util.Scanner;
public class NewNthPrime {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            boolean flag = false;
            int n = in.nextInt();
            int[] prime = new int[n];
            prime[0] = 2;
            int i = 3,j=1;

            while(j<n){
                for(int y=0;y<prime.length;y++){
                    if(prime[y]==0){
                        break;
                    }
                    else if (i%prime[y]==0){
                       flag = true;
                       break;
                    }
                }
                if(!flag){
                   prime[j++]=i;
                }
                flag =false;
                i+=2;
            }
            System.out.println(prime[n-1]);
        }
    }
}

这里我声明了一个名为 prime 的数组，它存储所有素数。 while 循环部分检查 array-prime[] 中存储的任何素数是否能整除数字“i”（仅是奇数。）。如果是，则标志变为真，我们跳过下一个数字“i”。在里面，当我还检查数组内的数字是否为零时，它会破坏 for 循环，因为素数数组中不能再有任何素数了。 现在，如果数字“i”不能被数组中的任何素数整除，则“flag”保持为 false，并将“i”放入数组 prime[] 中。

Answer 4

抱歉，我没有时间研究你的问题，但我想我们也可以通过这种方式找到第 n 个质数：

public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println("Enter nth position for which you want to find prime number ");
    Scanner sc  = new Scanner(System.in);       
    int k = sc.nextInt();
    findnthprimenumber(k);  
}

private static void findnthprimenumber(int k) {
    // TODO Auto-generated method stub
    int count=0;
    int j=2;    
    int l =0;
    while(l<k){
        for(int i=2;i<=j/2;i++)
        {
            if(j%i != 0)                
                continue;               
            else 
                count++;                                                    
        } 
        if(count == 0) {
            if(l==(k-1))
            System.out.println("Prime number on "+ k +"th position is "+ j);
            l++;
        }
        count=0;
        j++;
    }
}

Answer 5

这里使用单独的素数测试并加 6 以避免不必要的 isPrime() 检查：

import java.util.Scanner;

public class NthPrime {

private static boolean isPrime(int n) {
    int sqrt = (int) Math.sqrt(n)+1;
    if (n <= 3) { 
       return (n > 1);
    }
    if ((n%6 != 5)  && (n%6 != 1)) {
       return false;
    }
    for (int i = 5; i <= sqrt; i+=6) {
        if ((n % i == 0) || (n % (i+2) == 0)) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    Scanner IO = new Scanner(System.in);
    int nthprime;

    System.out.print("Enter value for n: ");
    nthprime=IO.nextInt();

    while(nthprime <= 0){
        System.out.print("Enter a positive value for n: ");
        nthprime=IO.nextInt();
    }

    if(nthprime == 1){
         System.out.println("Prime number " + nthprime + " is: "+2);
    }
    if(nthprime == 2){
        System.out.println("Prime number " + nthprime + " is: "+3);
    }

    if(nthprime > 2){

        int prime=2; 
        int num=-1;
        int ans = 0;

        while(prime < nthprime){
            num+=6;
            if (isPrime(num)) {
                prime++;
                ans = num;
                if (prime >= nthprime) break;
            }
            if ((isPrime(num+2)) && (prime < nthprime)) {
                prime++;
                ans = num+2;
                if (prime >= nthprime)  break;
            }
        }
            
        System.out.println("Prime number "+ nthprime + " is: "+ans);
    
    }

}

}

输出：

java NthPrime
Enter value for n: 1000
Prime number 1000 is: 7919