Java中的Eratosthenes筛（埃拉托斯特尼筛法）

Eratosthenes的筛子是一种古老的算法，可以查找直至给定数的素数。

算法

1.生成2到n（给定数）之间的整数。

2.每2个整数从2个标记开始计数。（2的倍数）

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