Erastothenes筛

Question

我正在尝试找出如何使用eratosthenes的筛子来找到1-300中的质数。我很难弄清楚，所以任何帮助都会很好！顺便说一句，我是编程新手，所以如果你能保持简单，最好是下面是我的代码(到目前为止)

    #include <stdio.h>
    #include <simpio.h>
    #include <genlib.h>
    #include <math.h>

    #define max 301

    main()
    {
         bool is_prime[max];
         int i, int1, j, n;
         int1=sqrt(max);

  for(n=0; n<=max; n++);
  {
           is_prime[n]=TRUE; //set everything to prime
  }

  is_prime[0]=FALSE; //false = NOT prime
  is_prime[1]=FALSE;
  for(i=2; i<int1; i++); //multiply starting from 2 end at 17
  {
           for(j=i; j<=(max/i); j++); //number being multiplied by
           {
                    n=(j*i);
                    is_prime[n]==FALSE; //all multiples of i are false
           }
  }
  if (is_prime[n]=TRUE); //print all prime numbers
  {
                        printf("%d", n);
  }
  getchar();
  }

Answer 1

你可以在这里看看它的实现。

Sieve实现：

bool arr[1000001];
int main()
{
    arr[0]=arr[1]=1;
    for(int i=4;i<1000001;i+=2)
        arr[i]=1;
    for(int i=3;i<1000001;i+=2)
    {
        if(!arr[i])
            for(int j=2;i*j<1000001;j++)
            {
                arr[i*j]=1;
            }
    }
    return 0;
}

有一个关于质数link的博客。

Answer 2

     class Program {

            static void Main(string[] args) {
                const byte disqualified = 1;
                const byte isprime = 2;


                int max = 300;

                byte[] numbers = new byte[max + 1];

                for (int outerIndex = 2; outerIndex < max + 1; outerIndex++) {
                    if (numbers[outerIndex] != disqualified) {
                        numbers[outerIndex] = isprime;
                        for (int innerIndex = outerIndex * 2; innerIndex < max + 1; innerIndex += outerIndex) {
                            numbers[innerIndex] = disqualified;
                        }
                    }
                }

                for (int i = 2; i < numbers.Length; i++) {
                    if (numbers[i] == isprime) {
                        Console.WriteLine("{0} is a prime number, thanks E my toga clad nerd buddy", i);
                    }
                }

                Console.ReadKey();
            }
        }

是的，C#示例-但接近于转换

结果如下：

​

​

Answer 3

使用不恰当的分号，除非已经指出。例如，当如下所示的块预期时，不执行

for(n=0; n<=max; n++);
{
....
}

像这样修复

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

#define max 301

int main(){
    bool is_prime[max];
    int i, int1, j, n;
    int1=sqrt(max);//17

    for(n=0; n<max; ++n){
        is_prime[n]=true;
    }

    is_prime[0]=false; //false = NOT prime
    is_prime[1]=false;

    for(i=2; i<int1; i++){
        if(is_prime[i])
            for(j=i+i; j<max; j+=i){
                is_prime[j]=false;
            }
    }
    for(n=2;n<max;++n){
        if(is_prime[n]==true)
            printf("%d ", n);
    }
    return 0;
}

#include <stdio.h>
#include <math.h>

#define max 300+1

int main(void){
    static is_prime[max]={0};
    int i, int1, n;
    int *p;

    int1=sqrt(max);
    is_prime[2] = 1;
    p = &is_prime[3];
    for(n=3; n<max; n+=2, p+=2)
        *p = 1;

    for(n=3; n<int1; n+=2)
        if(is_prime[n])
            for(i=n+n; i<max; i+=n)
                is_prime[i] = 0;
    for(n=2;n<max;++n)
        if(is_prime[n])
            printf("%d ", n);
    return 0;
}