1087.md

厄拉多塞的筛子

原文：https://www.javatpoint.com/sieve-of-eratosthenes

介绍

厄拉多塞筛是一种在给定极限内搜索所有素数的算法。它是由希腊天文学家厄拉多塞开发的。这个算法计算质数非常简单。一开始，我们把 2 到 n 之间的所有数字都写出来，我们把所有合适的 2 的倍数标记为复合数(因为 2 是最小的素数)，然后把所有合适的 3 的倍数标记出来，这个过程一直运行到 n。

厄拉多塞筛算法

input: an int n > 1
output: Each prime numbers from 2 to n

Let A be an array of Boolean values, indexed by integers 2 to n.
    initially all set to true.
    for i = 2, 3, 4, ..., not exceeding ?n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                A[j]: = false

    return all i such that A[i] is true

示例:

找出所有小于 25 的质数。

步骤:1 写出 2 到 25 之间的所有素数。

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

步骤:2 根据算法我们把所有合适的 2 的倍数标记为复合(因为 2 是最小的素数，也是列表的第一个数)

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

步骤:3 列表中 2 之后的下一个数字是 3，我们标记所有合适的 3 的倍数

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

步骤:4 列表中 3 之后的下一个数字是 5，还没有越过；我们标记所有适当的 5 的倍数

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

步骤:5 列表中 5 之后的下一个数字是 7，还没有越过；我们标记所有适当的 7 的倍数

2 34 56 78 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

步骤:6 该过程将运行至 n。

2 3 5 7 11 13 17 19 23

厄拉多塞筛的优势:

1. 这是一种非常有效的过滤素数的算法。
2. 它的执行率很低。

程序

厄拉多塞筛的 C++语言；

#include #include <conio.h>int main()
{
    int a, x, y;
    printf("Enter the number\n");
    scanf("%d", &a);

    int primes[a + 1];
    for(x = 2; x <= a; x++)
        primes[x] = x;

    x = 2;
    while ((x*x) <= a)
    {
        if (primes[x] != 0)
        {
            for(y = 2; y < a; y++)
            {
                if (primes[x] * y > a)
                    break;
                else
                    primes[primes[x] * y] = 0;
            }
        }
        x++;
    }

    for(x = 2; x <= a; x++)
    {
        if (primes[x] != 0)
            printf("%d\n", Prime numbers:[x]);
    }

    return 0;
}</conio.h> 

输出:

Enter the number
10
Prime numbers:
2 3 5 7

Java 程序

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

输出:

Enter the number
25
List of prime numbers upto given number are :
2 
3 
5 
7 
11 
13 
17 
19 
23

---