sieve of eratosthenes runtime error...

[sultan0104]

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

#include <iostream>
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<t; i++) {
		int n;
		cin >> n;
		cout << primeList[n] << endl;
	}
	
	return 0;
}

[lastchance]

On line 13 you have int j=i*i;

Ask yourself what that is (or even try printing it out!) when i =1000000.

[sultan0104]

Ohh okay, what if I changed int to unsigned long long, would it work??

[lastchance]

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.

[seeplus]

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:

#include <iostream>

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

[againtry]

#include <iostream>

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: 

[sultan0104]

@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))

[jonnin]

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.