埃氏筛法

砖业洋__

发布于 2023-05-06 16:39:51

1940

发布于 2023-05-06 16:39:51

文章被收录于专栏：博客迁移同步

给定整数n，请问n以内有多少个素数？

限制条件n≤106

如果要对许多整数进行素性测试，用埃氏筛法比较好

埃氏筛法原理：先将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去。

表中剩余的最小数字是3，它不能被更小的数整除，所以是素数。再将表中所有3的倍数都划去。

依次类推，如果表中剩余的最小数字是m时，m就是素数。然后将表中的所有m的倍数都划去。像这样反复操作，就能依次枚举n以内的素数。

2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
2	3	-	5	-	7	-	9	-	11	-	13	-	15	-	17	-	19	-
2	3	-	5	-	7	-	-	-	11	-	13	-	-	-	17	-	19	-

输入

输出

5(2、3、5、7、11共5个素数)

输入

1000000

输出

78498

import java.util.Scanner;

public class test1 {
    static int[] prime = new int[1000001]; // 记录每一个素数
    static boolean[] is_prime = new boolean[1000001];

    public static int sieve(int n) {
        int p = 0;
        is_prime[0] = is_prime[1] = false;
        for (int i = 2; i < n; ++i) {
            is_prime[i] = true;
        }
        for (int i = 2; i <= n; ++i) {
            if (is_prime[i] == true) {
                prime[p++] = i;
                for (int j = i << 1; j <= n; j += i) {
                    is_prime[j] = false;
                }
            }
        }
        return p;
    }
    // p记录了素数的个数，is_prime数组记录了测试范围每个数字是不是素数，prime数组记录每个素数
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        cin.close();
        int t = sieve(n);
        System.out.println(t + "个素数\n分别为：");
        for (int i = 0; i < t; ++i) {
            System.out.print(prime[i] + " ");
            if (i % 10 == 0) {
                System.out.println();
            }
        }
    }
}

用javascript实现如下：

<!DOCTYPE html>
<html>

<head>
    <meta http-equiv="Content-Type" content="text/html" charset="utf-8" />
    <title>素数复习</title>
    <script type="text/javascript">
        var prime = new Array, is_Prime = new Array;
        function isPrime(n) {
            var i, j, p = 0;
            for (i = 2; i < n; ++i) {
                is_Prime[i] = true;
            }
            for (i = 2; i < n; ++i) {
                if (is_Prime[i] == true) {
                    prime[p++] = i;
                    for (j = i << 1; j <= n; j += i) {
                        is_Prime[j] = false;
                    }
                }
            }
            return p;
        }
    </script>
</head>

<body>
    <pre><script type="text/javascript">
        document.writeln("1-100所有素数:");
        var p = isPrime(100), i = 0;
        for (i = 0; i < p; ++i) {
            document.write(prime[i] + '\t');
            if ((i + 1) % 5 == 0) document.writeln();
        }
    </script></pre>
</body>

</html>

运行结果：