Finding all prime numbers within a given range
The forums are right. You need only calculate primes up to Sqrt(N) to see if any integer up to N is a prime number. Here is a proof:
Case 1: N is a product of prime numbers < n. Trivial.
Case 2: Given some prime number A > r = Sqrt(N) is a factor of N...
N/A = B for some integer B. Rewrite A = (r+i) and B = (r+j). We have N = r^2 = AB = (r+i)(r+j) = r^2 + r(i+j) + ij.
From this we see that j = -ri/(i+1), where r > 0 and i > 0, so it must be that j < 0 for the equality to hold. Therefore, B < r.
B is evenly divisible by a prime number, p < r. And B is a factor of N, thus p must be a factor of N.
Therefore, for any non-prime, N, there must be a prime factor p < r. If you don't find p, then N must be prime.
Here is a simple solution:
int main() {
int max = 100;
int min = 0;
int sq = 0;
for (sq = 1; sq*sq<max; sq++){}
if (min <= 2)
for (int i = 1; i <= 2; i++){ cout << i << endl;}
min += ((min % 2 == 0) || (min == 0));
for (int i = min; i < max; i+=2)
{
bool prmFlag = true;
for (int j = sq; j > min - 1; j--)
{
if (j % 2 != 0)
if ((i % j == 0) && (j > 2) && (j != i))
prmFlag = false;
}
if ((prmFlag == true) && (i > 2))
cout << i << endl;
}
}
The forums are wrong (not surprising) and you are correct.
- Anonymous June 30, 2014Question for you: Is there is a code size/memory limit? If not, you can precompute everything and hardcode it. It will be super-fast then.