c++ - Prime number generation algorithm

Question

Please look at the following and see if you could advise.

cout << "2" << endl;
cout << "3" << endl;

ofstream of("Primes.txt");

unsigned long prime = 0;
unsigned long i = 1;
for (i = 1; i < 100000; i++)
{
    prime = ((i*2)+(i+1) + (i % 2));
    of << prime << endl;
}
of.close();
return 0;

The partially completed formula for calculating the nth prime

The nth prime is spat out but so is all of its prime factors

How to sieve through the list and find only primes.

5
7
11
13
17
19
23
25
29
31
35
37
41
43
47
49
53
55
59
61
65
67
71
73
77
79
83
85
89
91
95
97
101
103

OK I changed approaches a little - I will try implementing the sieve tonight - I am off to write Informatics test now, but here is my new implementation for the some primes.

vector<int> Primes;

bool IsPrime(int q)
{
    for(unsigned int i = 0; i < Primes.size(); i++)
    {
        if(q % Primes[i] == 0)
            return false;
    }
    return true;
}

int main()
{
    Primes.push_back(2);
    cout << "2" << " is prime" << endl;
    for (unsigned int i = 2; i < 1000000000; i++)
    {
        if(IsPrime(i))
        {
            Primes.push_back(i);
            cout << i << " is prime" << endl;
        }
    }
}

OK this does give primes but really uses a lot of mem. And grows slow over time as the vector gets longer.

Answer 1

Eliminating numbers dividable by prime numbers (2,3,5,7 etc.) is a not soo bad idea when you look for a list of (small) prime numbers but you should use the newly found prime numbers too to be sure that the list contains only primes (not only 2,3,5,7 but also those passing: 11,13,17 etc.)

For bigger primes (you just can't calculate the way explained if the numbers are too big as you need to check almost all numbers (say each 4-5 anyhow) from 1 to the number to check), the usual approach is to take a random big number and check if it passes Fermats Small Theorem with say 3,5,7 and 11 (IIRC the probability for it to be a non prime if it passes with just 3,5,7 and 11 is really improbable).

Check out Fermats primality test for a more hands on explanation.