素数算法 [英] Prime Number Algorithm

问题描述

谁能告诉我如何实现埃拉托色尼算法的C 筛？我需要生成素数，但我的算法是缓慢的。

Can anyone tell me how to implement Sieve of Eratosthenes algorithm in C? I need to generate prime numbers but my algorithm is slow.

我的code：

#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是素数要打印的范围内。

t is the number of test cases m and n is the range between which prime are to be printed.

推荐答案

您需要创建布尔大如你想找到的最大素数的数组。在开始的时候是完全初始化为true。

You need to create an array of booleans as big as the maximum prime number you want to find. At the beginning it's completely initialized to true.

在我个这样的阵列单元将是真实的，如果我是一个素数，还是假的，如果是不是。

The ith cell of such array will be true if i is a prime number, or false if it's not.

开始从 I = 2 迭代：它是素数，则设置为false，任何细胞具有2.进入指数多次到下一个素数（ I = 3 ），做同样的。转到下一任（这是 I = 5 ： I = 4 不是素数：数组[4] 设置为false在处理 I = 2 ），并一次又一次地这样做。

Start iterating from i=2: it's prime, then set to false any cell with an index multiple of 2. Go to the next prime number (i=3) and do the same. Go to the next prime (it's i=5: i=4 is not prime: array[4] was set to false while processing i=2) and do the same again and again.

这篇关于素数算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！