Prim számok szorzatára való általánosítható kiszürés? (c++)

Talán ez egyszerűbb és 'biztosabb':

#include <cstdlib>

#include <iostream>

#include <math.h>

using namespace std;

int main(){

bool prim_e;

int j, k;

for (int i = 2; i < 1000; i++){

j = (int)sqrt(i);

if (i == 2) cout << i << " ";

prim_e = (i % 2) != 0;

k = 3;

while ((prim_e) && (k < j )){

prim_e = (i % k) != 0;

k += 2;

}

if (prim_e) cout << i << " ";

}

system("PAUSE");

return 0;

}

Vagy akkor már ez:

#include<iostream>

#include<vector>

int main()

{

int N;

std::cout << "Give the upper limit of the prime search: ";

std::cin >> N;

if (N < 2) {

std::cout << "Really? Are you mocking me now?";

return 1;

}

bool NumberTable[N - 1];

for (int i = 0; i < N - 1; i++)

{

NumberTable[i] = true;

}

int startingIndex = 0;

std::vector<int> PrimeTable;

while (startingIndex < N - 1)

{

PrimeTable.push_back(startingIndex + 2);

for (int i = startingIndex; i < N - 1; i += startingIndex + 2)

{

NumberTable[i] = false;

}

do { startingIndex++; } while (!NumberTable[startingIndex]);

}

std::cout << "The prime numbers are:" << std::endl;

for (int i = 0; i < PrimeTable.size(); i++)

std::cout << PrimeTable[i] << std::endl;

std::cout<<"("<<PrimeTable.size() << "numbers in total)"<<std::endl;

}

A Eratoszthenészi szita az egyik leghatékonyabb prímkereső algoritmus. Prímkeresésre jelenleg nem ismeretes lineáris algoritmus, de ez a szita módszer azért közelíti. Igazából amit írtam, még nem is a teljes szitamódszer, kifelejtettem belőle, hogy elég a számok négyzetétől futtatni a belső for ciklust.

A helyes szitamódszerrel 100-ig terjedő számok esetében a fő algoritmus ha jól számolom, 128 iteráción megy végig, ami egyáltalán nem sok.