Hey Mafia, I got about the same task some time ago, and I wrote my code using a bitwise buffer to store all uneven numbers from 3 till the entered number, and then by using 'The Sieve of Eratosthenes' to sort out the numbers, simply picking the first one, and removing all that divides with this from the buffer. Then picking the next number like and dividing that thoughout the buffer.
The buffer will be like this;
3 5 7 9 11 13 15 ...
The program now finds 3, writes that to the screen, then does the following, by dividing out the buffer;
5 7 11 13 15 ...
Then it findes 5, and does the same:
7 11 13 ...
And so on, atm I'm trying mulithread the application using OpenMP (Started progamming this summer, so I'm not really good at multitheading applications yet), but as single threaded it's able to find all the primenumbers in the domain of 2-100.000.000 (5761454Primes) in just under 12seconds :), so it's quite effective. ^^that's using about 6mb of ram, and 2GHz, on my Laptop :), so I'm quite satisfied about the code. There are quicker ways, but my professor was impressed, as he was expecting a simple primetest algorithm, like take a number, use it in a modulo loop, to check if any number above to divided with it returns 0. This will work ofc. however it's VERY slow, and ineffecient, so use 'The Sieve of Eratosthenes' method, if you're able to. The bitwise buffer, is simply to use less memory :) - and to speed up things a bit :).
EDIT: The program only found 5761453, as I include 2 myself ofc :D
Btw; Code is quite messy and comments are written in danish, so wont really post it here, I'm sorry :o. Would simply be too messy to understand.
EDIT2: Here's a sample of my first sketch of a simple test algoritm, which does the job, but slowly:
//the calulation function.
void calc (unsigned int number, unsigned int i) //using "void" instead of "int", because the funktion doesn't need to return a value.
{
//define variables
bool Primecheck; //bool, that indicates wether the number is a prime or not (1 = Prime, 0 = Not a prime). Bool is used instead of int, since it only has to store 2 values (1 and 0).
unsigned int a = 0; //set a = 1, used to number the primes.
unsigned int j;
//write welcome message
cout << endl << "The program is finding primes in the domain of \"" << i << " ---> " << number << "\"" << endl; //tell the entered domain on the screen
out << "The program is finding primes in the domain of \"" << i << " ---> " << number << "\"" << endl; //same as above, just to the file.
//Calcul funktion
for (; i<=number; i++) //run the "i" loop, when "i" is less or equal (<=) to the input number., then +1 for each completed cycle.
{
Primecheck=1; //set the boolic value of primecheck = true, for the "i" loop. (to avoid a negativ loop, basically you'll have to set "not prime" each cycle, because everything is considered a prime at this point.)
//Filtering function, filters all non primes, and sets "primecheck = 0", if the tested number isn't a prime.
for (j=2; ((j < i) && (Primecheck==1)); j++) //run the "j" loop, run this until the "j" value is equal to the "i" value, by plussing 1, each time the cycle completes, starting from 2.
{if ((i%j)==0){Primecheck=0;}} //if "i" divided by "j" equals "0 in remainder", then set "Primecheck = 0" (number is not a prime). If i%j=0, then that's an devident, and therefore "i" isn't a prime number.
//Screen / file output
if(Primecheck!=0) //if number is a prime, then write output.
{
a++; //add +1 to "a", simply to be ready number the next prime.
cout << a << ". " << "Prime:\t"<< i << endl; //screen output - write "a" (1 as default (used to show which number in the prime number chain the prime number is)), then write "Prime:" then the number (the prime) "i".
}
//terminate for "i" loop, when "i" has reached the max domain number.
}
//write end message
cout << a << " primes was found; in the given domain!" << endl << endl; //announce the number of primes found on the screen.
//terminate function
}
^^Bad English, over commenting, and stuff, I wrote this code like a week after I learn'd that C++ even existed, so I know it sucks :D
// Skeen
