淘先锋技术网

首页 1 2 3 4 5 6 7

优化的朴素方法计算n是否为素数:

即从2到n的平方根,对每一个整数判断一次n是否可以被它整除,若有这样的数字,则n为合数,若无这样的数,则n为素数。代码如下:

int is_prime(int);
int is_prime(int number) {
    int i = ;
    for (; i * i <= number; i++) {
        if (number % i == )
            return ;
    }
    return ;
}

埃拉托色尼筛法(The Sieve of Eratoshenes):

步骤如下:
a>创建一个元素全部都被初始化为1的数组(代表真)。下标为素数的元素值最后会保持为1,而剩下的数组元素最后将被置为0。
b>从数组下标2开始(1不是素数也不是合数),每次处理首先找到一个值为1的数组元素,然后在剩余数组元素中,循环检测数组下标是否是那个值为1的元素的数组下标的倍数,若是,则将其元素值置为0。上述处理结束之后,值仍然为1的数组元素的下标就是素数。
实现如下:

void sieve();
void sieve() {
    int numbers[SIZE];
    int i = , k = ;
    for (i = ; i < SIZE; i++) numbers[i] = ;
    for (k = ; k < SIZE; k++) {
        if (numbers[k] == ) continue;
        for (i = k + ; i < SIZE; i++) {
            if (numbers[i] == ) continue;
            if (i % k == ) numbers[i] = ;
        }
    }
    for (i = ; i < SIZE; i++) if (numbers[i] == ) printf("%d\n", i);
}

结论

可以看出,对于优化的朴素方法,判断数n是否为素数的复杂度上限为 O(n1/2) ,则在小于n的数中判断其中每个数是否为素数的复杂度上限约为 O(n3/2) 。而埃拉托色尼筛法对于判断小于n的数中的素数的复杂度上限为 O(n) 。分析如下:
对于第一次筛选,遍历了 n 个元素,剩余总共的n/2个元素。接着第二次筛选遍历了 n/2 个元素,剩余 n/6 个元素。每次筛选素数 t 的倍数,剩余元素都变成了原来剩余元素个数的 t 分之一。设时间复杂度为 T(n) ,易知, T(n)<n+n/2+n/4+n/8+...+n/2t t 为n个数里面素数的个数。即T(n)<n×(112t+1),所以 T(n)=O(n)