埃拉託斯特尼篩法 Java

埃拉託斯特尼篩法是一種古老的演算法，用於查詢給定數字範圍內的質數。

演算法

1. 從 2 到 n（給定數字）生成整數。

2. 從 2 開始，標記每個第 2 個整數。（2 的倍數）

3. 現在，從 3 開始，標記每個第 3 個整數。（3 的倍數）

4. 最後，從 5 開始，標記每個第 5 個整數。（5 的倍數）

程式

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);
         }
      }
   }
}

輸出

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

George John

更新於： 25-Jun-2020

4K+ 瀏覽

開啟你的職業生涯生涯

完成本課程，獲得認證

開始