c – 素数算法

谁能告诉我如何在C中实现 Sieve of Eratosthenes算法？我需要生成素数但我的算法很慢.

我的代码：

#include <stdio.h>

int prime(long int i)
{
    long int j;
    int state = 1;
    for(j=2;j<i;j++)
    {
        if((i%j)==0){state=0;break;}
    }
    return state;
}

int main()
{
    int t;
    long int m,n,i;
    scanf("%d",&t);
    while(t--) {
        scanf("%d %d",&m,&n);
        for(i=m;i<=n;i++)
        {
            if(i==1){
                //do nothing for 1
            } else{
                if(prime(i))printf("%d\n",i);
            }
        }
    }
    return 0;
}

t是测试用例的数量m,n是要打印质数的范围.

解决方法

您需要创建一个与您要查找的最大素数一样大的布尔数组.在开始时它完全初始化为true.

如果i是素数,则此类数组的第i个单元格将为true,否则为false.

从i = 2开始迭代：它是素数,然后将索引倍数为2的任何单元格设置为false.转到下一个素数(i = 3)并执行相同操作.转到下一个素数(它是i = 5：i = 4不是素数：当处理i = 2时,数组[4]被设置为假)并且一次又一次地执行相同操作.

c – 素数算法

解决方法

相关文章