埃拉托斯特尼筛法

2024 年 8 月 29 日 | 阅读 3 分钟

引言

埃拉托斯特尼筛法是一种用于查找给定范围内所有素数的算法。它由希腊天文学家埃拉托斯特尼发明。该算法非常简单，可以计算素数。首先，我们写出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 7~~8 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

埃拉托斯特尼筛法的优点

它是一种非常有效的筛选素数的算法。
它的实现成本很低。

程序

埃拉托斯特尼筛法的C++语言

#include <stdio.h>
#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;
}

输出

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<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 the number
25
List of prime numbers upto given number are :
2 
3 
5 
7 
11 
13 
17 
19 
23

下一个主题维吉尼亚密码

← 上一个下一个 →

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

关注我们

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

PWA 教程

埃拉托斯特尼筛法

引言

埃拉托斯特尼筛法的算法

示例

埃拉托斯特尼筛法的优点

程序

埃拉托斯特尼筛法的C++语言

Java程序

相关帖子

PWA 教程

维吉尼亚密码

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器