c - 前N个素数优化

Question

我已经看到了一定数量的与该论点相关的问题，但是一旦没有人完全符合我的要求，我就会提出一个新问题。我必须计算前 N 个质数(示例中为 1000)。我提出了一个可以正常工作但根本没有优化的工作算法。

#include<stdio.h>
#define MAX_NUMBERS 1000
int main()
{
   int prime[MAX_NUMBERS]={0};
   int filled=0;
   prime[filled++]=2;
   int n=0,i=0;
   while(filled<MAX_NUMBERS) {
      for( n=prime[filled-1]+1; ;n++ ) {
         int found =0;
         for( i=0; i<filled && (found==0); i++ ) {
            if( (n%prime[i]) == 0 ) {
               found = 1;
            }
         }
         if( !found ) {
            break;
         }
       }
       /* we know that this always exists */
       prime[filled++]=n;
   }
   for(i=0;i<filled;i++) {
      printf( "prime number %d\n", prime[i] );
   }
   return 0;

有人知道如何优化吗？在这种情况下，是否有任何算法更改可以提供帮助？

Answer 1

最好的方法是通过像下面这样最简单且非常有效的筛分方法:-

Sieve of eratosthenes