# Does this algorithm find prime numbers only?

I'm writing code to help find prime numbers within a certain range. Here's my general pseudo-code:

1. Iterate through every single number in the range.
2. If the number is 2, 3, 5, or 7; then mark it as a prime number.
3. If the number is NOT divisible by 2, 3, 5, or 7; then it's also a prime number.

Think about it. Checking divisibility by 2 already removed even numbers. Three, five, and 7 are other fundamental prime numbers, so any other non-prime number has to be a divisor of any of these. I tested this algorithm with all numbers between 1-100, and it worked. But would it work for all numbers?

• Try it for 121. Dec 17, 2014 at 7:55
• Most modern definitions do not treat $1$ as a prime number Dec 17, 2014 at 7:57
• What made you think 3, 5, and 7 are "fundamental", but all later primes aren't? Dec 18, 2014 at 2:35

For any integer $n \ge 2$ either $n$ is prime or $n$ has a prime factor less than or equal to $\sqrt{n}$. So, if you are only finding prime numbers within a range of $1$ through $N$, then you need to check divisibility by every prime less than or equal to $\sqrt{N}$.

Since you were only focused on the range $1$ through $100$, you need to check for divisibility by all primes up to $\sqrt{100} = 10$. So testing $2$, $3$, $5$, and $7$ is sufficient. However, if you go up to $121 = 11^2$ or higher, testing only $2$, $3$, $5$, and $7$ will not work.

• Ah, thank you very much for the informative comment. So I'll just change my code a bit to check it against all prime numbers between 1 and sqrt(N). Dec 17, 2014 at 8:28
• @user3894009 note though that your code will start producing the correct answer, but it will be monumentally slower :)
– Ant
Dec 17, 2014 at 21:49

Your ideas are interesting for the problem of "finding all prime numbers within a range". The fact that you verified that your idea works for all numbers below $100$ (except for $1$, which isn't considered prime, but let's put that aside) proves that your algorithm is correct for the range $[2,100]$. Not optimal by any means, but it is.

Your algorithm relies on a simple observation : a number ($\geq2$) is prime if and only if it can be divided by another number than $1$ and itself. You noticed that it works for numbers below $100$, and others have already pointed out that it fails for $121 = 11\times 11$. With this observation, you might deduce that you need to check also the divisibility by prime numbers higher than $7$ like $11$, $13$...

But where should we stop ? There is an infinity of prime numbers and you can't possibly check divisibility by all of them ! This issue is solved by noticing that a number $n$ can't have all its prime divisors higher than $\sqrt n$. Hence, to verify the primality of $149$, you need to check for divisibility by all the primes below $\sqrt{149}$, that is to say $2,3,5,7,11$.

This yields another issue : how could we find what are the prime numbers below $\sqrt{n}$ ? Well, since we did your check for every number below $n$ (because you want all the primes in the range), we can reuse the previous results : simply iterate through all your results up to $\sqrt n$ to have all these "fundamental primes for $n$" as you said.

However, as you may begin to understand now, this is not efficient : the further we go, the more numbers we have to check for divisibility with. Even if we managed to have a pretty good algorithm if we would like primality of one given $n$, maybe we could do better for a whole range.

If you know that a number $n$ is divisisible by a prime $p$, what can you say of $n+p$ ? It is divisible by $p$ too ! And to know this, you didn't even had to calculate a division or a modulo !

This is the basis of the Erathostenes' sieve, which is way more efficient than yours. You should click on the links for all the details and implementation : the gif at the top of the page is worth a thousand words.

TL;DR : No, it doesn't work for all numbers, because you stopped at $7$. If you define your range as $[2,n]$, you need to include all the prime numbers below $\sqrt{n}$. This is why it works for $100$ but not $121$.

• Thanks. I learnt something new in the hopes of simply finding an explanation for an observation. I just wanted a better way to find prime numbers than the primitive method learnt in my programming class. Dec 17, 2014 at 8:34
• "This issue is solved by noticing that a number n can't have a prime divisor higher than sqrt(n)." -- of course what you mean to say is that a number n cannot have all of its prime divisors be higher than sqrt(n) Dec 17, 2014 at 11:01
• @aPaulT : Of course, thanks. I have edited the post. Dec 17, 2014 at 11:43
• " for verifying that 147 is prime, ..."? The wording does not look appropriate, considering that 147 is not prime. Dec 18, 2014 at 1:27
• @ypercube : Yeah, I should have written "to verify the primality of...", but even, this wasn't a good example because we can stop after we verify $3$. I changed the wording and used $149$. Thanks for the feedback ! Dec 18, 2014 at 7:54

Hint:
1. Prime numbers greater than 5 are either can be formed as $6k-1$ or $6k+1$.
2. If x can not be divided by 2, 3, 5, 7,..., and k (k is the greatest prime number less than square root of x.) then x is prime.

No, I believe you are incorrectly implementing Eratosthenes Sieve, in which you mark the multiples of prime numbers as non prime, starting with $2$. Your algorithm fails for $121 = 11 \times 11$, as user7530 kindly pointed out.