有关素数的基础算法 素性测试 埃氏筛法

所谓素数，是指恰好有两个约数的正整数。因为n的约数都小于n，所以只需要检查2 ~  n-1之间所有的整数是否整除n就能判定n是不是素数。如果d是n的约数，那么n/d也是n的约数。由n = d * n / d可知min(d，n / d) 

，所以只需要检查2 ~ 

之间的所有整数就足够了。同理可知，整数分解和约数枚举都可以在

时间完成。

判定单一的一个数是不是素数，素性测试：
 

bool is_prime(int n)/**< 判定一个数是不是素数 ，假设输入的数都是正整数*/
{
    for(int i = 2;i * i <= n; i++)
    {
        if(!(n % i))
            return false;
    }
    return n != 1;/**< 1是例外 */
}

如果只对一个数进行素数测试，通常

的算法就足够了。但如果要对许多整数进行素性测试，则有更高效的算法。要枚举n以内的素数，可以用埃氏筛法：这是一种古老的算法，首先，将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去，然后表中剩余最小的素数是3，将表中所有3的倍数也都划去。以此类推，如果表中剩余最小的素数是m的话，就将表中所有m的倍数都划去，像这样反复操作，就能依次枚举n以内的素数，埃氏筛法的时间复杂度仅有

，接近线性：

bool is_prime[MAX];
int prime[MAX];
int sieve(int n)/**< 枚举n以内的素数 */
{
    /**< 返回n以内素数的个数，素数存在prime数组里*/
    int p = 0;
    for(int i = 0;i <= n; i++)
        is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    for(int i = 2;i <= n; i++)
    {
        if(is_prime[i])
        {
            prime[p++] = i;
            for(int j = i * 2;j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return p;
}