C++ 筛法求素数

*本文部分内容摘自维基百科（Wikipedia)。

素数（即质数），指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。

确定一个数n是否为素数的基本方法是 试除法：将n除以每个大于1且小于等于n的平方根之整数m。若存在一个相除为整数的结果，则n不是素数；反之则是个素数。

这种方法过于繁琐，实际几乎没有应用。

实际运用中会使用到“筛法”。以埃拉托斯特尼筛法为例，这是一种简单且历史悠久的筛法，用来找出一定范围内所有的素数。

筛法原理

筛法的原理是从2开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。

简单来说，在筛法的过程中，由于从2开始，每次都会筛去倍数，即筛去了不符合素数条件（没有1以及本身之外的因子），那么剩下的（被跳过的）则必然是素数。

算式

给出要筛数值的范围n，找出 ${\sqrt {n}}$ 以内的素数p1,p2,…,pk $p_1,p_2,\dots ,p_$ 。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去……。

示意图（来自维基百科）

C++实现

#include<iostream>
using namespace std;
#define NUM 100000

bool isPrime[NUM+1]; // a[NUM]范围是0～NUM-1

int main()
{
    for (int i=2; i<=NUM; ++i)
        isPrime[i] = true; //将所有数初始化为true
    for (int i=2; i<=NUM; ++i)
    {
        if (isPrime[i]) // 找出素数，筛除素数的倍数
        {
            for (int j=2*i; j<=NUM; j += i) // 从isPrime[2i]开始筛 每次步进一个i
                isPrime[j] = false;
        }
    }
    // 输出结果
    for (int i=2; i<=NUM; ++i)
    {
        if (isPrime[i])
            printf("%d\n", i);
    }
    return 0;
}