Оптимизировать скорость премьер номер Сито (Java)

Question

Я работаю по методу в Java, который создает логическое массив IsPrime:

boolean[] isPrime; 

, в которых простые числа помечены «истина» и остальные с 'ложный'.
Пока я на него, я бы также хотел бы подсчитать количество Primes найдено:

int numPrimesFound; 

Основная идея заключается в том, чтобы использовать Решето Эратосфена. До сих пор мой метод выглядит следующим образом:

public Sieve(final int limit) { 

    long startTime = System.currentTimeMillis(); 

    boolean[] isPrime = new boolean[limit]; 
    this.isPrime = isPrime; 

    for (int i=3; i<=limit ;i+=2) { 
     isPrime[i] = true;      //sets all even numbers to true 
    } 

    isPrime[2] = true; 
    numPrimesFound = 1;       //special case of '2' 

    for (int i = 3; i * i <= limit; i += 2) { 
     if (isPrime[i] == true) { 
      for (int j = i; i * j <= limit; j += 2) { 

       isPrime[i * j] = false;   //has a multiple ==> not a prime 

       numPrimesFound++;     //doesn't work yet 
      } 
     } 
    } 

    long stopTime = System.currentTimeMillis(); //measuring execution time 
    System.out.println("Sieve: " + (stopTime - startTime) + " milliseconds.") 

} 

Так что моя проблема в том, что

numPrimesFound++: 

не работает, так как решето устанавливает значение некоторых не простых чисел к «ложным» более чем один раз (например, 45 bcs 3 * 15 = 45 и 9 * 5 = 45).
Значит, кто-нибудь знает, как я могу переписать эту программу, чтобы все лишние числа задавали «false» только один раз?

Или, вообще говоря, может ли кто-нибудь предложить способы ускорения метода?

Answer 1

У вас есть путаница:

numPrimesFound ++; это хорошо, но она должна быть вне цикла для (Int J = я, я * J < = предел; J + = 2)

ваш основной цикл должен идти дальше (или вы забыли простые числа больше, чем SQRT (предел)

for (int i = 3; i < limit; i += 2) 

это нормально в Эратосфена решето, чтобы отметить несколько раз «не простые» числа.

и я * Й < предел норвежских крон, если он становится больше, чем междунар (он становится отрицательным)

Результат такой же, но только с

final int limit=40000; // 50 000 is too big ! 

заменить вам внутренний цикл с этим, и вы можете пойти 1000000. по крайней мере

for (int z = i*2; z<limit; z+=i) 
    isPrime[z] = false;   //has a multiple ==> not a prime 

И вы могли бы использовать BitSet

Answer 2

Если вы используете BitSet вы можете попросить его cardinality.

public BitSet primes(final int limit) { 

    long startTime = System.currentTimeMillis(); 
    BitSet isPrime = new BitSet(limit); 
    // A bitSet starts all zeros but with a sieve - evrything must start prime. 
    isPrime.flip(0, limit); 

    // 0 and 1 are not prime 
    isPrime.clear(0); 
    isPrime.clear(1); 

    for (int i = 2; i * i <= limit; i += 2) { 
     if (isPrime.get(i)) { 
      // Remove all multiples of i. 
      for (int j = 2; i * j <= limit; j += 1) { 
       isPrime.clear(i * j); 
      } 
     } 
    } 

    long stopTime = System.currentTimeMillis(); //measuring execution time 
    System.out.println("Sieve: " + (stopTime - startTime) + " milliseconds."); 
    return isPrime; 
} 

public void test() { 
    BitSet primes = primes(50); 
    System.out.println("Primes: " + primes); 
    System.out.println("Count: " + primes.cardinality()); 
} 

Я также исправил пару ошибок в вашей логике. Например. ваша внутренняя петля сделала шаг j2, и ваш внешний контур не удалял все четные числа (началось с 3).

Вы, безусловно, можете улучшить это - Google - ваш друг. :)

Answer 3

ok ..Вот что я придумал

long startTime = System.currentTimeMillis(); 
int limit = 100000; 
boolean[] isPrime = new boolean[limit+1]; 

Arrays.fill(isPrime, true); 
isPrime[0] = false; 
isPrime[1] = false; 
int numPrimesFound = limit-1;       

System.out.println("Sqrt is:" + Math.sqrt(limit)); 
for (int i=2; i < Math.sqrt(limit);i++) { 
    if (isPrime[i] == true) { 
     int inc = 0; 
     while (true) { 
      int j = (i*i) + (inc*i); 
      if(j > limit) break; 
      if (isPrime[j]) { 
       isPrime[j]= false; 
       numPrimesFound--;  
      } 
      inc++; 
     } 
    } 
} 

System.out.println("Number of Primes" + numPrimesFound); 
for (int i = 2; i < limit;i++) { 
    if (isPrime[i]) 
     System.out.println("Prime#:" + i); 
} 
long stopTime = System.currentTimeMillis(); //measuring execution time 
System.out.println("Sieve: " + (stopTime - startTime) + " milliseconds."); 

Answer 4

Вот моя версия:

import java.util.BitSet; 
import java.util.Scanner; 

public class Main { 

public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); 
    System.out.println("Enter the interval limit: "); 
    int limit = sc.nextInt(); 
    int max = (int) Math.sqrt(limit); 
    long start = System.currentTimeMillis(); 
    BitSet intArray = new BitSet(limit); 

    // 1 is not prime 
    intArray.set(0); 

    // 2 is the first prime number, so the first step is to filter out all even numbers 
    for (int i = 2; (2 * i) - 1 < limit; i++) { 
     intArray.set((2 * i) - 1); 
    } 

    //all remaining number will be odd 
    int currentNumber = 3; 
    // i is the multiplicator and will be adjusted with the current number , in order to avoid repetition 
    int i = 3; 
    int temp; 

    while (currentNumber <= max) { 
     // flag multiple of the current prime number 
     do { 
      temp = (currentNumber * i); 
      if (temp > limit) break; 
      intArray.set(temp - 1); 
      i = i + 2; 
     } while (temp <= limit); 
     //all non-prime numbers until now are already flagged, therefore we can find the next prime number by checking the set-status. 
     while (currentNumber + 2 <= limit) { 
      currentNumber += 2; 
      if (!intArray.get(currentNumber - 1)) { 
       i = currentNumber; 
       break; 
      } 
     } 
    } 

    int b = 0; 
    for (int n = limit -1 ; n > 0; n--){ 
     if (!intArray.get(n)){ 
      b = n +1; 
      break; 
     } 
    } 
    System.out.println("There are " + (limit - intArray.cardinality()) + " PRIMES and the biggest is: " + b); 
    System.out.println("Time in total: " + ((System.currentTimeMillis() - start)/1000.0) + "s"); 
} 
} 

Чтобы проверить 100 млн номеров, она должна ca. 0,7 с на настольном ПК i7 3770k.