Есть ли более эффективный способ написать следующий код простого числа?

Question

У меня есть следующий код, который разбрасывает простые числа от 1 до N. Друг придумал это решение, но я считаю, что есть более эффективный способ написания этого кода.Например, сделать так, чтобы if (i%j!=0) {System.out.print (i + " ");}.Тем не менее, я обнаружил, что случайные числа выплескивались повсюду ...

import java.util.Scanner;

public class AllPrime {


public static void main(String[] args) {

    System.out.println("Enter a number:\n");
    Scanner input = new Scanner(System.in);
    int a = input.nextInt();

    for (int i = 2; i < a; i++) {
        boolean primeNum = true;
        for(int j=2; j<i; j++) {
            if (i%j==0) {
                primeNum =false;
            }
        }
        if (primeNum) {
            System.out.print(i + " ");
            }
        }
    }
}

Answer 1

Посмотрите на правильные сита, такие как Сито Эратосфена . Вам не нужно каждый раз проверять %.

Answer 2

public static boolean [] createPrimes (final int MAX)
{
         boolean [] primes = new boolean [MAX];
         // Make only odd numbers kandidates...
         for (int i = 3; i < MAX; i+=2)
         {
                primes[i] = true;
         }
         // ... except No. 2
         primes[2] = true;

         for (int i = 3; i < MAX; i+=2)
         {
                /*
If a number z is already eliminated
(like No. 9), because it is a multiple of - 
for example 3, then all multiples of z 
are already eliminated.
                */
                if (primes[i] && i < MAX/i)
                {
                        int j = i * i;
                        while (j < MAX)
                        {
                                if (primes[j])
                                        primes[j] = false;
                                j+=2*i;
                        }
                }
        }
        return primes;
}

обновлено после комментария Уилла Несса:

Повышает скорость до 2/1, проверяет 100 миллионов ints за 5 секунд на моем одноядерном 2Ghz.

Answer 3

for(int j=2; j<i; j++) {
            if (i%j==0) {
                primeNum =false;
            }
        }

Это не очень эффективный алгоритм, но, по крайней мере, поместите туда break ...

Answer 4

private static void generatePrimes(int maxNum) {

    boolean[] isPrime = new boolean[maxNum + 1];
    for (int i = 2; i <= maxNum; i++)
        isPrime[i] = true;

    // mark non-primes <= N using Sieve of Eratosthenes
    for (int i = 2; i * i <= Math.sqrt(maxNum); i++) {

    // if i is prime, then mark multiples of i as nonprime
    if (isPrime[i]) {
        for (int j = i; i * j <= maxNum; j++)
        isPrime[i * j] = false;
        }
    }

    // count primes
    int primes = 0;
    for (int i = 2; i <= maxNum; i++)
        if (isPrime[i]) {
        System.out.println("Prime - " + i);
        primes++;
        }
            System.out.println("The number of primes <= " + maxNum + " is "+ primes);
    }