простые числа — сито стека Эратосфена

В настоящее время я работаю над проектом, в котором я хочу вычислить все простые числа.
Когда я компилирую (MINGW Windows Comp.), Программа падает и возвращает случайный номер ошибки.
Вот код, который я написал:

http://pastebin.com/4vVnAM2v

/*
Sieb des Eratosthenes
*/

#include <iostream>
#include <math.h>
using namespace std;

main()
{
//variablendeklaration
unsigned int nmax=100;
unsigned int i,j,erg;
bool prim[nmax];

//Initialisieren
prim[0]=false;
prim[1]=false;

//array prim[i] erstellen
for(i=2;i<nmax;i++)
{
prim[i]=true;
}for(i=2;i<nmax;i++) //alle Primzahlen durchlaufen
{
if(prim[i] == true) //auf Prim prüfen
{
for(j=2;j<nmax;j++) //multiplizieren und wegstreichen
{
erg = j * i;
prim[erg] = false;
}
}
}

for(i=2;i<nmax;i++)
{
cout << prim[i] << endl;
}}

0

Решение

С этой точки зрения:

            erg = j * i;
prim[erg] = false;

вы собираетесь в конечном итоге получить доступ за пределами prim, так как оба i а также j может иметь значение до nmax - 1, так erg будет иметь максимальное значение (nmax - 1) * (nmax - 1), Вы должны проверить это условие и сломать, если erg >= nmaxнапример,

            erg = j * i;
if (erg < nmax)          // if i * j still within bounds
prim[erg] = false;   // set prim[i * j] to false
else                     // else i * j now >= nmax
break;               // break out of loop and try next i value
1

Другие решения

Еще один способ решить эту проблему — избежать лишних шагов в цикле:

for(i=2; i < nmax; i++)
{
if(prim[i] == true)
{
for (j = 2 * i; j < nmax; j += i) // state j at 2i, increment by i
{
prim[j] = false;
}
}
}

Это имеет эффект 1) не зацикливание nmax вложенные элементы (уменьшая вашу общую сложность с O (n ^ 2) до O (n * (n / 2 + n / 6 + n / 10 + …), что фактически равно O (n log n) и 2) не требует дополнительной проверки границ, так как вы никогда не выходите за границы в своем цикле.

1

По вопросам рекламы [email protected]