C语言 素数算法

Prime Number Algorithm

提问by jaykumarark

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

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

My 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;
}

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

t是测试用例的数量 m，n 是要打印素数的范围。

回答by peoro

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.

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

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

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

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=4is not prime: array[4]was set to false while processing i=2) and do the same again and again.

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

回答by Toomtarm Kung

In my opinion, your algorithm slow because you calculate the inessential number. try this code

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

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;

}

回答by jaykumarark

Here is actually very simple code that use the Sieve of Eratosthenes algorithm. works for all positive int.

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

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

回答by Rooke

Marc B's link shows a nice and simple algorithm which is correct, written by NSLogan. I wrote a slight modification to it to show some size/speed tradeoffs. I thought I'd share for interest's sake.

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

First, the code:

首先，代码：

#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;
}

Since this uses sqrt, to compile use: gcc prime.c -lm

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

I've compared three different ways of storing the boolean variables that peoro suggested. One method actually uses bits, the second takes an entire byte, and the last uses an entire machine word. A naive guess about which is fastest might be the machine word method, since each flag/boolean is dealt with more 'naturally' by your machine. The timings to calculate the primes up to 100,000,000 on my machine were as follows:

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

Bits: 3.8s Chars: 5.8s M-words: 10.8s

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

It is interesting to note that even all the ugly bit-shifting necessary to represent a boolean with only one bit is still faster overall. My conjecture is that caching and locality-of-reference seem to outweigh the extra ~3 instructions. Plus, you end up using 1/nth the memory of the n-bit-machine-word method!

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

回答by pankaj

Though it's very old post, Following is my try to generate the prime number using "Sieve of Eratosthenes"algorithm.

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

#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]);
    }
  }

}

Hope this will help someone.

希望这会帮助某人。

回答by Brendan

Fist step is to recognize that it's trivial to split it into arbitrary sized blocks; and that you do NOT need an array (or bitfield) for every number. For example, if you only care about numbers from 100000 to 110000, then to mark all numbers that are divisible by 3 as "not prime" you can do "for( index = 3 * (100000+3-1)/3; index < 110000; index += 3) {". For a more flexible example:

第一步是认识到将其拆分为任意大小的块是微不足道的；并且您不需要每个数字的数组（或位域）。例如，如果您只关心从 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);
        }
    }

The second step is to realize that you don't need to care about every number (and the for( value = 2; value < sqrt( block_end_value-1); value++)above is inefficient). For example, if you've already marked numbers that are divisible by 2 as "not prime" then there is no reason to care if numbers are divisible by 4, 6 or 8; and if you've already marked numbers that are divisible by 3 as "not prime" then there is no reason to care if numbers are divisible by 6, 9 or 12; and ... Essentially you only want to test if a number is divisible by another prime number. This means that to find prime numbers in the range 100000 to 110000 you first want to find prime numbers in the range 0 to sqrt(110000); and if you want to find prime numbers in the range 0 to sqrt(110000) you want want to find prime numbers in the range 0 to sqrt(sqrt(110000)); and ....

第二步是意识到你不需要关心每一个数字（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)) 范围内的素数；和 ....

The third step is to realize that it can be accelerated by copying repeating patterns. You can create a 2-bit pattern (representing "is divisible by 2") and copy those 2 bits everywhere. In the same way you can create a 6-bit pattern (representing "is divisible by 2 or 3") and copy those 6 bits everywhere. In the same way you can create a 39916800-bit pattern (representing "is divisible by 2, 3, 4, 5, 6, 7, 8, 9, 10 and 11") and copy that 39916800-bit pattern everywhere. Of course nothing prevents you from pre-generating a pattern and storing it in your program's code.

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

The fourth step is to realize that multiples of 2 are too trivial to store and by not storing them you halve the memory consumption of all tables and patterns (and any stored/pre-generated pattern).

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

By combining the third and fourth steps above; a pre-generated pattern representing "is divisible by 2, 3, 4, 5, 6, 7, 8, 9, 10 and 11" will cost 19958400 bits, or about 2.38 MiB. On its own the first part of this pattern will also be usable for finding prime numbers from 1 to the first prime number that is larger than 11 (which in this case would be numbers from 1 to 13).

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

The fifth step is to realize that if you already have a pattern you can use it to find "N = the next "not marked yet" prime number", copy the existing pattern N times, then mark multiples of N as "not prime"; and end up with a larger pattern. For example; if you have a pattern representing "is divisible by 2, 3, 4, 5, 6, 7, 8, 9, 10 and 11", you'd skip over 12 (because its not prime according to the existing pattern); copy the pattern 13 times, then mark the numbers that are divisible by 13 as "not prime" and end up with a pattern representing "is divisible by 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 and 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".

第六步是意识到一旦你有一个足够大的模式来满足你想要的范围，你就可以不用复制来填充缺失的除数。例如，如果您只想要 1 到 6227020800 范围内的质数；那么你可以取一个表示“可以被 2、3、4、5、6、7、8、9、10、11、12 和 13 整除”的模式，然后标记可以被 14 范围内的素数整除的数字到 6227020800 为“非素数”。

By combining all of the above; if you want to find prime numbers in the range 1000000000 to 11000000000; then you'd start by finding prime numbers in the range 1 to sqrt(11000000000); and to do that you'd copy a pre-generated pattern and extend it until you have a table that would be large enough to represent prime numbers in the range 1 to sqrt(11000000000); then copy that extended pattern and fill in the missing numbers to generate a table representing prime numbers in the range 1 to sqrt(11000000000); then create a table for prime numbers in the range 1000000000 to 11000000000 and initialise the memory by copying data from the "extended pre-generated pattern" into it, then use the table of prime numbers in the range 1 to sqrt(11000000000) to find prime numbers that haven't already been incorporated into the "extended pre-generated pattern" to find numbers that still need to be marked as "not prime" that you need to generate the table for numbers from 1000000000 to 11000000000.

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