В настоящее время я работаю над проектом, в котором я хочу вычислить все простые числа.
Когда я компилирую (MINGW Windows Comp.), Программа падает и возвращает случайный номер ошибки.
Вот код, который я написал:
/*
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;
}}
С этой точки зрения:
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
Еще один способ решить эту проблему — избежать лишних шагов в цикле:
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) не требует дополнительной проверки границ, так как вы никогда не выходите за границы в своем цикле.