I'm writing code to help find prime numbers within a certain range. Here's my general pseudo-code:
- Iterate through every single number in the range.
- If the number is 2, 3, 5, or 7; then mark it as a prime number.
- 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?
Best Answer
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.