Алгоритм сита Эратосфена

Question

Я сейчас читаю "Программирование: принципы и практика с использованием C ++" , в Глава 4 есть упражнение, в котором:

Мне нужно создать программу для вычисления простых чисел от 1 до 100 с использованием алгоритма Сита Эратосфена.

Это программа, которую я придумал:

#include <vector>
#include <iostream>

using namespace std;

//finds prime numbers using Sieve of Eratosthenes algorithm
vector<int> calc_primes(const int max);

int main()
{
    const int max = 100;

    vector<int> primes = calc_primes(max);

    for(int i = 0; i < primes.size(); i++)
    {
        if(primes[i] != 0)
            cout<<primes[i]<<endl;
    }

    return 0;
}

vector<int> calc_primes(const int max)
{
    vector<int> primes;

    for(int i = 2; i < max; i++)
    {
        primes.push_back(i);
    }

    for(int i = 0; i < primes.size(); i++)
    {
        if(!(primes[i] % 2) && primes[i] != 2)
             primes[i] = 0;
        else if(!(primes[i] % 3) && primes[i] != 3)
             primes[i]= 0;
        else if(!(primes[i] % 5) && primes[i] != 5)
             primes[i]= 0;
        else if(!(primes[i] % 7) && primes[i] != 7)
             primes[i]= 0;
    }   

    return primes;
}

Не самый лучший или быстрый, но я все еще нахожусь в начале книги и мало что знаю о C ++.

Теперь проблема в том, что max не больше 500, все значения печатаются на консоли, если max > 500 не все напечатано.

Я что-то не так делаю?

П.С .: Также будет приветствоваться любая конструктивная критика.

Answer 1

Вот моя реализация, не уверенная, если 100% правильно, хотя: http://pastebin.com/M2R2J72d

#include<iostream>
#include <stdlib.h> 

using namespace std;
void listPrimes(int x);

int main() {

    listPrimes(5000);
}

void listPrimes(int x) {
    bool *not_prime = new bool[x];
    unsigned j = 0, i = 0;

    for (i = 0; i <= x; i++) {
        if (i < 2) {
            not_prime[i] = true;
        } else if (i % 2 == 0 && i != 2) {
            not_prime[i] = true;
        }
    }

    while (j <= x) {
        for (i = j; i <= x; i++) {
            if (!not_prime[i]) {
                j = i;
                break;
            }
        }
        for (i = (j * 2); i <= x; i += j) {
            not_prime[i] = true;
        }
        j++;
    }

    for ( i = 0; i <= x; i++) {
        if (!not_prime[i])
            cout << i << ' ';
    }

    return;
}

Answer 2

Попробуйте этот код, он будет вам полезен при использовании банка вопросов java

import java.io.*;

class Sieve

{

    public static void main(String[] args) throws IOException

    {

        int n = 0, primeCounter = 0;

        double sqrt = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        System.out.println(“Enter the n value : ”);

        n = Integer.parseInt(br.readLine());

        sqrt = Math.sqrt(n);

        boolean[] prime = new boolean[n];

        System.out.println(“\n\nThe primes upto ” + n + ” are : ”);

        for (int i = 2; i<n; i++)

        {

            prime[i] = true;

        }

        for (int i = 2; i <= sqrt; i++)

        {

            for (int j = i * 2; j<n; j += i)

            {

                prime[j] = false;

            }

        }

        for (int i = 0; i<prime.length; i++)

        {

            if (prime[i])

            {

                primeCounter++;

                System.out.print(i + ” “);

            }

        }

        prime = new boolean[0];

    }

}

Answer 3

Вот более эффективная версия алгоритма Sieve of Eratosthenes, которую я реализовал.

#include <iostream>
#include <cmath>
#include <set>

using namespace std;

void sieve(int n){
    set<int> primes;
    primes.insert(2);
    for(int i=3; i<=n ; i+=2){
        primes.insert(i);
    }       

    int p=*primes.begin();
    cout<<p<<"\n";
    primes.erase(p);

    int maxRoot = sqrt(*(primes.rbegin()));

    while(primes.size()>0){
        if(p>maxRoot){
            while(primes.size()>0){
                p=*primes.begin();
                cout<<p<<"\n";
                primes.erase(p);        
            }
            break;
        }

        int i=p*p;  
        int temp = (*(primes.rbegin()));
        while(i<=temp){
            primes.erase(i);
            i+=p;
            i+=p;
        }
        p=*primes.begin();
        cout<<p<<"\n";
        primes.erase(p);
    }
}

int main(){
    int n;
    n = 1000000;
    sieve(n);                
    return 0;
}