c – 素数算法

前端之家收集整理的这篇文章主要介绍了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&C++相关文章