c语言--素数的查找

查找素数

普通版

void prime_num(int n)
{
    int i = 0;
    int j = 0;
    for(i = 2; i < n; ++i){
        for(j = 2; j <= i; ++j){
            if(i % j == 0){
                break;
            }
        }
        if(j > i / 2){
            printf("%d ", i);
        }
    }
}

普通版改进

从2到i找i的约数是很浪费的，若整数i从2到根号i都不能被i整除,说明i就是素数

void prime_num(int n)
{
    int   i = 0;
    int   j = 0;
    float t = 0;
    for(i = 0; i < n; ++i){
        t = sqrt(i);
        for(j = 2; j <= t; ++j){
            if(i % j == 0){
                break;
            }
        }
        if(j > t){
             printf("%d ", i);
        }
    }
    printf("\n");
}

这种方法只适合比较少量的素数的判度,的值达到很大的时候,会很慢的说

筛选法

以空间来换取时间.

void prime_num(int n)
{
    char *tag = (char *)malloc(n + 1);
    int     i = 0;
    int     j = 0;
    float   t = 0;
    memset(tat, 0, n + 1);
    t = sqrt(n);
    //第一层循环只要i到达t就停止了,因为n约数至少有一个是在根号t以内,所以
    //只要2-->t就可以把质数筛完
    for(i = 2; i <=t; ++i){
        if(!tag[i]){
            for(j = 2 * i; j <= n; j = j + i){
                tag[j] = 1;  //把质数i的整数倍筛除掉
            }   
        }
    }
    //n以内的质数的状态则都存在数组里面
}