Sito Eratostenesa

Sito Eratostenesa to algorytm wyznaczania liczb pierwszych z zakresu od 2 do n. Istotą algorytmu jest wykreślanie z danego zbioru 2..n wszystkich wielokrotności kolejnych liczb (zaczynając od dwójki), które nie zostały jeszcze wykreślone. Wystarczy uwzględnić tylko liczby z przedziału od 2 do wartości całkowitej pierwiastka z n. Niewykreślone liczby będą liczbami pierwszymi z podanego zakresu.

// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Sito Eratostenesa
 * @author kodatnik.blogspot.com 
 */
public class SitoEratostenesa {
 
 public static void main(String args[]) {
    
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj n: " );   
    
  // pobieramy od użytkownika n (zakres)
  int n = sc.nextInt();    
      
  // obliczamy liczbę iteracji 
  int liczbaIteracji = (int) Math.sqrt(n);

  // zakładamy tablicę o rozmiarze n+1
  // domyślnie będzie ona miała wartości false
  boolean[] jestPierwsza = new boolean[n + 1];
       
  // zmieniamy na true (zakładamy, że wszysktie liczby
  // z przedziału 2..n są pierwsze)
  for (int i = 2; i < n+1; i++) jestPierwsza[i] = true;

  // główna pętla usuwająca wielokrotności kolejnych liczb pierwszych
  // poprzez wstawianie na odpowiednim indeksie ablicy wartości false
  for (int i = 2; i <= liczbaIteracji; i++) {

   // sprawdzamy czy pierwsza, jeśli nie to następna iteracja
   if (jestPierwsza[i]) {
    // jeśli pierwsza usuwamy jej wielokrotności wstawiając false na odpowiedni indeks tablicy
    for (int j = i * i; j <= n; j += i) jestPierwsza[j] = false;
   }
  }

  // pętla wyświetlająca liczby pierwsze z pzedzialu 2..n
  // jeśli wartość na indeksie i jest równa true to jest to liczba pierwsza
  for (int i = 2; i <= n; i++)
   if (jestPierwsza[i]) System.out.print(i + " ");
 }
}

Przykładowe uruchomienie programu:

Podaj n: 20
2 3 5 7 11 13 17 19