3
$\begingroup$

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?

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

5 Answers 5

Reset to default
31
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ 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). $\endgroup$
    – user3894009
    Dec 17, 2014 at 8:28
  • 1
    $\begingroup$ @user3894009 note though that your code will start producing the correct answer, but it will be monumentally slower :) $\endgroup$
    – Ant
    Dec 17, 2014 at 21:49
11
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – user3894009
    Dec 17, 2014 at 8:34
  • 1
    $\begingroup$ "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) $\endgroup$
    – aPaulT
    Dec 17, 2014 at 11:01
  • $\begingroup$ @aPaulT : Of course, thanks. I have edited the post. $\endgroup$
    – Traklon
    Dec 17, 2014 at 11:43
  • $\begingroup$ " for verifying that 147 is prime, ..."? The wording does not look appropriate, considering that 147 is not prime. $\endgroup$
    – ypercubeᵀᴹ
    Dec 18, 2014 at 1:27
  • $\begingroup$ @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 ! $\endgroup$
    – Traklon
    Dec 18, 2014 at 7:54
2
$\begingroup$

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.

Add your code.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

For an algorithm to find primes within a certain range, yes, taking the primes under the square root of the maximum value will suffice. However, what if this was any maximum value?, and what happens when your square root (of 1000 for example) isn't an integer?, i'd say that you need to find the primes below the square root first, then run the function.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .