埃拉托斯特尼筛法 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

更新于：2020-06-25

4K+ 次浏览

开启你的 职业

完成课程即可获得认证

开始
广告