c语言素数问题，萌新求教

Question

输出1~500000以内的素数，共有41538个，每两个素数之间有一个空格。全部输出后，不要再输出空格或回车换行符。

使用下面的原始算法，大概需要计算7分钟。请改进算法，使计算时间缩短在0.2秒钟以内。耗时比是2100倍。

#include <stdio.h>
int main()
{
    int i,j,cnt=0;
    for(i=2;i<=500000;i++)
    {
        cnt=0;
        for(j=1;j<=i;j++)
        {
            if(i%j==0)cnt++;
        }
        if(cnt==2)printf("%d ",i);
    }
}

改进思路：

1、如果是2、3、5、7的倍数，就不要去判断

2、否则，每个数i只判断到sqr(i)即可

Answer 1

#include <stdio.h>
#include <math.h>

int isPrimeNumber(int a);//判断素数

int main() 
{
    int i,j,k;
    int s = isPrimeNumber(2);
    printf("%d",s);
    for(i=2;i<=500000;i++){
        if(isPrimeNumber(i)){
            printf("%d ",i);
        }
    }
    return 0; 
}

int isPrimeNumber(int a){
    int s = (int)sqrt(a);
    for(int i=2;i<=s;i++){
        if(a%i==0){
            return 0;
        }
    }
    return 1;
}