1

我试图弄清楚如何使用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();
  }
4

6 回答 6

2

你可以看看这里的实现。

筛子实现： 

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

并且有一篇关于素数链接的博客。

于 2013-06-26T11:06:47.300 回答
1 
     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# 示例 - 但足够接近转换

结果是：

在此处输入图像描述

于 2013-06-03T07:16:52.927 回答
1 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class exp {

private int size;
private boolean[] arr;
public exp(int a){
    size = a;
    arr = new boolean[size];
}
public void initialize(){
    for(int i=2;i<size;++i)
        arr[i] = true;

    arr[0] = arr[1] = false;
}

public void precompute(){
    int i=2;
    while(i<size){
        if(arr[i]){
            for(int j=2*i; j<size; j=j+i)
                arr[j] = false;
        }
        i++;
    }
}
public String printX(int as){
    int counter = 0;
    String ans="",b = " ";
    for(int i=0; i<size ; ++i){
        if(arr[i]){
            ans += String.valueOf(i) + b;
            counter++;
        }
        if(counter == as)
            break;
    }
    return ans;
}
public static void main(String[] args) throws NumberFormatException, IOException {

    long a = System.currentTimeMillis();
    exp e = new exp(50000);
    e.initialize();
    e.precompute();
    long b = System.currentTimeMillis();

    //System.out.println(b-a);
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    int N;
    for(int i=0;i<t;++i){
        N = Integer.parseInt(br.readLine());
        if(N == 1)
            System.out.println("1");
        else
            System.out.println(e.printX(N));
    }
}

}
于 2014-08-16T15:03:50.293 回答
1

以下是 C++ 中的示例实现：

void sieve_of_eratosthenes(int n)
{
    bool *sieve = new bool[n+1];

    // Initialize
    sieve[0]=false;
    sieve[1]=false;
    sieve[2]=true;

    for(int i=3;i<n+1;++i)
        sieve[i]=true;

    // Actual sieve
    for(int i=1; i<n+1; ++i)
        if(sieve[i]==true)
            for(int j=2;j*i<n+1;++j)
                sieve[j*i]=false;

    // Output
    cout << "Prime numbers are: " <<endl;
    for(int i=0;i<n+1;++i)
        if (sieve[i])
            cout << i <<endl;

    delete [] sieve;
}

int main()
{
    int n = 70;
    sieve_of_eratosthenes(n);
}
于 2013-11-09T03:23:08.047 回答
1

除了已经指出外，不宜使用分号。例如，当块如以下意图时不执行

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;
}
于 2013-06-03T10:50:38.983 回答
0

为了找到 1-300 的素数，您必须使用一种称为埃拉托色尼筛法的技术，这是从给定范围内查找素数列表的最有效方法。

这是代码：

#include <bits/stdc++.h>
using namespace std;

const int SIZE=100010;
int status[SIZE]={1};

int sieve(){
    for(int i=0;i<=SIZE;i++)
        status[i]=1;

    for(int i=2;i<=SIZE;i++){
        if(status[i]==1){
            for(int j=2*i;j<=SIZE;j+=i){
                status[j]=0;
            }
        }
    }

}

int main(){
    sieve();
    //check from 2 to 300 which one is prime
    for(int i=2;i<300;i++){
        if(status[i]==1)
            printf("%d ",i);
    }

}
于 2016-11-02T06:13:55.777 回答