You are missing something, the divisors of a number start repeating after the squareroot of the number, so, the prime test would be more efficient if it breaks when it reaches the sqrt of the number. And also remember that there are several formulas that *MAY* return a prime number, you always have to test it. I have made an algorythm that only takes 18 seconds to calculate the first 100000 prime numbers in my athlon xp 2500+ (I made it first for python and is my first progam in C++ so I apologize if it doesn`t have much style).
#include <iostream>#include <math.h>using namespace std;int main() { start: unsigned long m,x,d,mo,rc; bool p; string f; cout << "how many primes do you want? "; cin >> m; cout << "\nfrom what number start? "; cin >> x; if (x <= 2 && m >= 1) { cout << "2\n"; x = 2; m--; } if (x <= 3 && m >= 1) { cout << "3\n"; m--; } if (x%2 == 0) { x++; } while (m >= 1) { p = true; d = 1; rc = sqrt(x); while (d <= rc && p) { d++; d++; mo = x%d; if (mo == 0) { p = false; } } if (p) { cout << x << "\n"; m--; } x = x + 2; if (m <= 0) { break; } } cout << "repeat? y/n "; cin >> f; if (f == "y") { goto start; } else { return 0; } }
