java - 验证某些数字是否为素数的程序？

Question

好的，所以我编写了这个程序来验证一个数字是否是素数。我不知道如何编写一个程序来验证所有 < n 的数字都是素数。你能帮我吗？

import javax.swing.*;

public class Main {

    public static void main(String[] args) {
        int i;
        int n;
        boolean nPrime=true;
        n = Integer.parseInt(JOptionPane.showInputDialog("Entrer un numero"));

        for (i = 2; i < n; i++) {
            if (n % i == 0) {
                nPrime = false;


            }
        }
        if (nPrime) {

            System.out.println("Le numero " + n + " est prime");
        } else
            System.out.println("Le numero " + n + " n'est pas prime");


    }
}

Answer 1

如果您有很多查询，我的答案会有更好的时间复杂度。我们可以在 O(nlg(n)lg(n)) 中预先计算所有小于 1000005 的素数，然后对于每个查询，它需要 O(1 ) 检查数字是否为素数的时间。使用的算法是Seive Of Eratosthenes

如果您想了解更多有关算法的信息，请点击以下链接: http://www.geeksforgeeks.org/sieve-of-eratosthenes/

static int MAX = 1000005;
public static void preComputeSeive(){
    Arrays.fill(isPrime, true);

    isPrime[0] = isPrime[1] = false;

    for(int i = 2; i < MAX; i++){
        if(isPrime[i]){
            for(int j = i+i; j < MAX; j+=i){
               isPrime[j] = false; 
            }
        }
    }
}

static boolean isPrime[] = new boolean[MAX];
public static void main(String args[]) throws IOException
{
  int n = Integer.parseInt(JOptionPane.showInputDialog("Entrer un numero"));

  if(n >= MAX){
    System.out.println("Enter a valid number");
    return;
  }      

  preComputeSeive();
    // count primes
  for (int i = 2; i <= n; i++) {
  if (isPrime[i]) {
    System.out.println("Le numero " + i + " est prime");
  } else {
    System.out.println("Le numero " + i + " n'est pas prime");
  }
}

}