Java >> Java tutorial >  >> Java

Si af Eratosthenes i java

Sieve of Eratosthenes er den ældgamle algoritme til at finde primtal op til et givet tal.

Algorithme

1. Generer heltal fra 2 til n (angivet tal).

2. Tællende fra 2 markér hvert 2. heltal. (multipler af 2)

3. Start nu med 3 markere hvert tredje heltal. (multipler af 3)

4. Endelig markerer du fra 5 hvert 5. heltal. (multipler af 5)

Program

import java.util.Scanner;

public class SievePrimeFactors  {
   public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      System.out.println("Enter a number");
      int num = sc.nextInt();
      boolean[] bool = new boolean[num];
     
      for (int i = 0; i< bool.length; i++) {
         bool[i] = true;
      }
      for (int i = 2; i< Math.sqrt(num); i++) {
         if(bool[i] == true) {
            for(int j = (i*i); j<num; j = j+i) {
               bool[j] = false;
            }
         }
      }
      System.out.println("List of prime numbers upto given number are : ");
      for (int i = 2; i< bool.length; i++) {
         if(bool[i]==true) {
            System.out.println(i);
         }
      }
   }
}

Output

Enter a number
50
List of prime numbers up to given number are :
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47

Java tag