素数算法

Question

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

我的代码:

#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是要打印质数的范围.

Answer 1

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

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

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

Answer 2

在我看来,你的算法很慢,因为你计算了不必要的数字.试试这段代码

int isPrime(int number){

    if(number < 2) return 0;
    if(number == 2) return 1;
    if(number % 2 == 0) return 0;
    for(int i=3; (i*i)<=number; i+=2){
        if(number % i == 0 ) return 0;
    }
    return 1;

}

Answer 3

这是使用Eratosthenes Sieve算法的非常简单的代码.适用于所有积极的int.

int is_prime(int n){
  int p;
  for(p = 2; p < n; p++){
    if(n % p ==0 && p != n)
      return 0;    
  }
  return 1;
}