1

エラトステネスのふるいを使って 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 
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 
     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

以下は、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 に答える
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 に答える