8

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

我的代码：

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

4

7 回答 7

12

您需要创建一个布尔数组，该数组与您要查找的最大素数一样大。一开始它完全初始化为真。

如果是素数，则i此类数组的第 th 个单元格将为真，否则为假。i

从 开始迭代i=2：它是素数，然后将索引倍数为 2 的任何单元格设置为 false。转到下一个素数 ( i=3) 并执行相同操作。转到下一个素数（它是i=5: i=4is not prime:array[4]在处理时设置为 false i=2）并一次又一次地做同样的事情。

于 2011-01-26T19:35:10.527 回答
6

在我看来，您的算法很慢，因为您计算了无关紧要的数字。试试这个代码

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;

}
于 2013-01-19T20:51:35.250 回答
5

这实际上是使用埃拉托色尼筛算法的非常简单的代码。适用于所有积极的人int。

int is_prime(int n){
  int p;
  for(p = 2; p < n; p++){
    if(n % p ==0 && p != n)
      return 0;    
  }
  return 1;
}
于 2017-03-04T22:48:52.010 回答
3

Marc B 的链接显示了一个不错且简单的算法，该算法是正确的，由 NSLogan 编写。我对其进行了轻微修改以显示一些大小/速度的权衡。我想我会为了兴趣而分享。

首先，代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <time.h>

#define USE_BITS

#ifdef USE_BITS
#define alloc_prime char *prime = calloc(i/8+1,sizeof(*prime));
#define set_not_prime(x) prime[x/8]|= (1<<(x%8))
#define is_prime(x) (!(prime[x/8]&(1<<(x%8))))
#endif

#ifdef USE_CHAR
#define alloc_prime char *prime = calloc(i+1,sizeof(*prime));
#define set_not_prime(x) prime[x] = 1
#define is_prime(x) (prime[x] == 0)
#endif

#ifdef USE_SIZE_TYPE
#define alloc_prime size_t *prime = calloc(i+1,sizeof(*prime));
#define set_not_prime(x) prime[x] = 1
#define is_prime(x) (prime[x] == 0)
#endif

 
int main(){
    int i;
    printf("Find primes up to: ");
    scanf("%i",&i);
 
    clock_t start, stop;
    double t = 0.0;
       
    assert((start = clock())!=-1);
       
    //create prime list
    alloc_prime;
    int c1, c2, c3;
    if(!prime){
    printf("Can't allocate %zu bytes.\n",i*sizeof(*prime));
    exit(1);
    }
       
    //set 0 and 1 as not prime
    set_not_prime(0);
    set_not_prime(1);

    //find primes then eliminate their multiples (0 = prime, 1 = composite)
    for(c2 = 2;c2 <= (int)sqrt(i)+1;c2++){
      if(is_prime(c2)){
        c1=c2;
        for(c3 = 2*c1;c3 <= i+1; c3 += c1){
          set_not_prime(c3);
        }
      }
    }
       
    stop = clock();
    t = (double) (stop-start)/CLOCKS_PER_SEC;
       
    //print primes
    for(c1 = 0; c1 < i+1; c1++){
        if(is_prime(c1))printf("%i\n",c1);
    }
    printf("Run time: %f\n", t); //print time to find primes

    return 0;
}

由于这使用sqrt, 来编译使用：gcc prime.c -lm

我比较了 peoro 建议的存储布尔变量的三种不同方式。一种方法实际上使用位，第二种方法使用整个字节，最后一种方法使用整个机器字。关于哪个最快的天真猜测可能是机器字方法，因为每个标志/布尔值都由您的机器更“自然”地处理。在我的机器上计算素数高达 100,000,000 的时间如下：

位：3.8s 字符：5.8s M 字：10.8s

有趣的是，即使是表示只有一位布尔值所需的所有丑陋位移，总体上仍然更快。我的猜想是缓存和引用位置似乎超过了额外的〜3条指令。另外，您最终会使用 n 位机器字方法的 1/n 内存！

于 2011-01-28T21:27:26.107 回答
1

第一步是认识到将其拆分为任意大小的块是微不足道的；并且您不需要每个数字的数组（或位域）。例如，如果您只关心从 100000 到 110000 的数字，那么要将所有可被 3 整除的数字标记为“非质数”，您可以执行“ for( index = 3 * (100000+3-1)/3; index < 110000; index += 3) {”。对于更灵活的示例：

    for( value = 2; value < sqrt( block_end_value-1); value++ ) {
        for( index = value  * (block_state_value+value -1)/value; index < block_end_value; index += value ) {
            mark_not_prime(index - block_state_value);
        }
    }

第二步是要意识到你不需要关心每个数字（for( value = 2; value < sqrt( block_end_value-1); value++)以上是低效的）。例如，如果您已经将可被 2 整除的数字标记为“非质数”，那么没有理由关心数字是否可被 4、6 或 8 整除；如果您已经将可被 3 整除的数字标记为“非质数”，则没有理由关心数字是否可被 6、9 或 12 整除；和......基本上你只想测试一个数字是否可以被另一个素数整除。这意味着要查找 100000 到 110000 范围内的素数，您首先要查找 0 到 sqrt(110000) 范围内的素数；如果你想找到 0 到 sqrt(110000) 范围内的素数，你想找到 0 到 sqrt(sqrt(110000)) 范围内的素数；和 ....

第三步是意识到可以通过复制重复模式来加速。您可以创建一个 2 位模式（表示“可被 2 整除”）并将这 2 位复制到任何地方。以同样的方式，您可以创建一个 6 位模式（表示“可被 2 或 3 整除”）并将这 6 位复制到任何地方。以同样的方式，您可以创建一个 39916800 位模式（表示“可被 2、3、4、5、6、7、8、9、10 和 11 整除”）并将该 39916800 位模式复制到任何地方。当然，没有什么能阻止您预先生成模式并将其存储在程序代码中。

第四步是意识到 2 的倍数太小而无法存储，并且通过不存储它们，您可以将所有表和模式（以及任何存储/预生成的模式）的内存消耗减半。

通过结合上面的第三步和第四步；表示“可被 2、3、4、5、6、7、8、9、10 和 11 整除”的预生成模式将花费 19958400 位，即大约 2.38 MiB。就其本身而言，该模式的第一部分也可用于查找从 1 到大于 11 的第一个素数（在本例中为从 1 到 13 的数字）的素数。

第五步，意识到如果你已经有一个模式，你可以用它找到“ N = the next "not marked yet" prime number”，将现有模式复制N次，然后将N的倍数标记为“非素数”；并以更大的模式结束。例如; 如果你有一个模式表示“可被 2、3、4、5、6、7、8、9、10 和 11 整除”，你会跳过 12（因为根据现有模式它不是素数）；复制该模式 13 次，然后将可被 13 整除的数字标记为“非质数”，最终得到一个表示“可被 2、3、4、5、6、7、8、9、10、11 整除的模式, 12 和 13"。

The sixth step is to realize that once you have a pattern large enough for the range you want, you can fill in the missing divisors without copying. For example, if you only want prime numbers in the range from 1 to 6227020800; then you can take a pattern representing "is divisible by 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 and 13" and then mark numbers that are divisible by prime numbers in the range from 14 to 6227020800 as "not prime".

通过结合以上所有；如果你想找到 1000000000 到 11000000000 范围内的素数；那么你首先要找到 1 到 sqrt(11000000000) 范围内的素数；为此，您将复制一个预先生成的模式并将其扩展，直到您有一个足够大的表来表示 1 到 sqrt(11000000000) 范围内的素数；然后复制该扩展模式并填写缺失的数字以生成表示从 1 到 sqrt(11000000000) 范围内的素数的表格；然后为 1000000000 到 11000000000 范围内的素数创建一个表，并通过将“扩展预生成模式”中的数据复制到其中来初始化内存，然后使用 1 到 sqrt(11000000000) 范围内的素数表来查找尚未并入“

于 2019-08-11T21:16:52.873 回答
1

虽然这是很老的帖子，但以下是我尝试使用“埃拉托色尼筛”算法生成素数。

#include <stdio.h>

#define NUM 8000        /* Prime Numbers in the Range.  'Range + 2' actually. */

int main()
{
  int a[NUM] = {0};         /* Array which is going to hold all the numbers */
  int i , j;

  /* initializing array from 2 to given number + 2, assuming the first prime number is 2 */
  for(i = 2,j=0; i < NUM+2, j<NUM; i++, j++) 
  {
    a[j] =i;
  }


  for(i = 0; i < NUM; i++ ) 
  {
    int num = a[i];

    /* If number is not 0 then only update the later array index. */
    if(num != 0) 
    {
      for (j = i+1; j < NUM; j++) 
      {
        if( (a[j]%num == 0) ) 
        {
            a[j]=0;
        }
      }
    }
  }


  for(i = 0; i < NUM; i++) 
  {
    /* Print all the non Zero *Prime numbers* */
    if(a[i] != 0) 
    {
      printf("%d \n", a[i]);
    }
  }

}

希望这会对某人有所帮助。

于 2015-07-09T16:14:56.323 回答
0

Tootarm Kung 的回答很棒，非常感谢。

然而，我偶然发现了一个警告：可能会在 32 位和64 位上(i*i)溢出，产生不正确的结果，即在使用 32 位整数时不会被识别为素数。i>46340i>30370004992147483647

为了避免整数溢出，可以替换(i * i)<=number为i <= number / i

现在，为了避免双重除法，代码可以写成如下：

int isPrime(int number){
    if(number < 2) return 0;
    if(number == 2) return 1;
    if(number % 2 == 0) return 0;
    int j;
    for(int i=3; ((j=number/i) >= i); i+=2){
        if(number - (j * i) == 0 ) return 0;
    }
    return 1;
}
于 2020-07-30T15:53:19.697 回答