埃拉托色尼质数筛选法

以前夏季学期的时候接触过埃氏筛选法，不过自己当时不太理解。今天看的时候有点感觉，大概用到的是每个合数都能写成几个质数相乘的格式，因此如果不能被比该数小的质数整除的话，该书一定也是质数。并且我们已知2是最小的质数，所以从2开始筛选。

以下程序可以输出不超过n的所有质数。（当然鉴于数组的大小是有限的，因此n也是有范围的）

#include

int main(){
    int num[1000], n;
    scanf("%d",&n);
    for(int i = 2; i <= n; i++){
        num[i] = i;
    }
    for(int i = 2; i <= n; i++){
            if(num[i] != 0){
                for(int j = i+1;  j <= n ; j++){
                   if(num[j] % num[i] == 0) num[j] = 0; 
                }
            }
    }
    for(int i = 2; i <= n ; i++){
        if(num[i] != 0 ) printf("%d ",num[i]);
    }
}

 但我觉得这样应该不是最快的，毕竟某些已经被筛去的合数还是参与了取余操作。并且一些操作显然没有必要进行。例如在找小于100的质数时，虽然53是质数，但是显然后面已经没有以53为因数的数了，毕竟53×2=106＞100。也就是说，在找100以内质数时，循环到第53个数时已经足够了，没有必要进行后面的操作了。

经过观察我们很容易发现，当我们以m为因数消去后面的合数时，2m、3m 、……、(m-1)m已经在前面的操作中消去了，所以现在需要消去的是m^2、m(m+1) ……但是如果m^2已经大于n的话，后续的操作已经没有意义了，所以实际上循环到√n（向下取整）就可以了。

补充：写完才忽然理解书上算法的意义，上面的思路写出来还不是最简单的，更快速的应该是这种写法：

#include
#include

int main(){
    int num[10000], n;
    scanf("%d",&n);
    for(int i = 2; i <= n; i++){
        num[i] = i;
    }
    for(int i = 2; i <= sqrt(n); i++){
            if(num[i] != 0){
                for(int j = i*i;  j <= n ; j=j+i){   /*考虑到i*i+m，当m小于i时肯定不能被i整除，筛不去。因此直接加i。到这里我才发现最开始
                                                       的思路是有问题的。一开始想的是将因数为前面出现过的质数的数筛去，其实这里已经表明，
                                                       与其筛去因数是质数的，还不如直接筛去某一质数的倍数，连判断都可以省去*/
                                                            
                   num[j] = 0; 
                }
            }
    }
    for(int i = 2; i <= n ; i++){
        if(num[i] != 0 ) printf("%d ",num[i]);
    }
}