### sieve of eratosthenes runtime error...

Hi. I recently just learned the sieve of eratosthenes to generate prime numbers, but evrytime i want to run the code, the program just exits before i even input the values.... i wonder why, here's the code, thx

 ``1234567891011121314151617181920212223242526272829303132`` ``````#include using namespace std; bool elim[1000001] = {false}; int primeList[77778]; void soe() { int ind = 1; for (int i=2; i<1000001; i++) { if (!elim[i]) { primeList[ind] = i; ind++; for (int j=i*i; j<1000001; j += i) { elim[j] = true; } } } } int main() { int t; cin >> t; soe(); for (int i=0; i> n; cout << primeList[n] << endl; } return 0; }``````
On line 13 you have int j=i*i;

Ask yourself what that is (or even try printing it out!) when i =1000000.
Ohh okay, what if I changed int to unsigned long long, would it work??
Why don't you try it? Both i and j would have to be declared of that type.

It wouldn't crash, but it's not very good code. It's simpler to deal with arrays elim[] and primeList[] separately. Then you can put a constraint on i whilst evaluating elim only (i.e. i * i < upper bound). Only once elim[] has been fully set up should you go and look for primes to put in primeList[].

Incidentally, you are asking for trouble with the repeated appearance of magic number 1000001; (you might forget to change all occurrences of it). Also, you are presuming rather a lot by setting primeList to the size that you do.
Last edited on
Well 1,000,000 * 1,000,000 is 1,000,000,000,000

The maximum value of an unsigned long long is 18,446,744,073,709,551,615 which is > 1,000,000,000,000.

There are also other issues. Perhaps something like which will calculate all the primes and display the first 50:

 ``123456789101112131415161718192021222324252627`` ``````#include using namespace std; using T = unsigned long long; constexpr T MaxNum {1'000'001}; bool elim[MaxNum] {}; T primeList[MaxNum] {2}; void soe() { T ind {1}; for (T i = 3; i * i < MaxNum; i += 2) if (!elim[i]) { primeList[ind++] = i; for (T j = i; j < MaxNum; j += i) elim[j] = true; } } int main() { soe(); for (T i {}; i < 50; ++i) cout << primeList[i] << ' '; }``````

 ``` 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 ```

Last edited on
 ``12345678910111213141516171819202122232425262728293031323334353637383940`` ``````#include using namespace std; bool elim[100000]{true}; void soe() { elim[0] = true; elim[1] = true; for ( int i = 2; i * i < 100000; i++) { for (int j = i*i ; j < 100000; j += i) { elim[j] = 1; } } } int main() { soe(); int t{0}; while (1) { cout << "Enter a number: " and cin >> t; if(elim[t] == false) cout << t << " is"; else cout << t << " is not"; cout << " prime\n"; } return 0; }``````

 ```Enter a number: 0 0 is not prime Enter a number: 1 1 is not prime Enter a number: 2 2 is prime Enter a number: 3 3 is prime Enter a number: 4 4 is not prime Enter a number: 6 6 is not prime Enter a number: 7 7 is prime Enter a number: 125 125 is not prime Enter a number: 129 129 is not prime Enter a number: 123 123 is not prime Enter a number: 1213 1213 is prime Enter a number: ```
@lastchance
Oh, I see. So you mean smth like

for (ll i = 2; i < 1000001; i++) {
if (!elim[i]) {
primeList[ind] = i;
ind++;
}
}

@seeplus
That's pretty good, maybe I'll just add a new variable to count the primes that are already listed to find the specific nth prime

@againtry
I'll probably use that to check if a number is a prime or not, I'm actually able to do that but with the old method (check if its divisible from 2 to sqrt(n))
there are a bunch of primality tests you can look up -- these don't use brute force or a master list of primes but perform various algorithms that either converge on an answer (likely prime or absolutely not prime) or flat out tell you up to some size (not sure if any of the fast ones cover 64 bit ints though).
at the very least, a lot of these can tell you for sure not-prime, so worst case is after doing a couple of them you have to fall back to checking. Take a look if you want to play... its an interesting subject.
Topic archived. No new replies allowed.