Tests for prime numbers
I'm told to list the prime numbers from 7 to 150 .
I know how to do it the slow way by one by one checking the numbers till 150. But in an exam condition I can't possibility do that .
Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ?
$\endgroup$ 89 Answers
$\begingroup$That seems like a silly test question, but you can use the Sieve of Eratosthenes. Start with all numbers from 7 to 150 and start removing multiples of integers greater than 1. Animation from the Wikipedia link:
As for proving a number is prime, it is actually much easier to show that a number is not prime. Maybe you have some more idea of what you might see on a test, but those seem like irritating questions.
$\endgroup$ 6 $\begingroup$The illustrated answer above is cool.
Here is something that might be quicker for you during an exam.
The prime numbers between $7$ and $150$ are all the neighbors of multiples of $6$, except:
- Those that end with $5$
- $49$
- $77$
- $91$
- $119$
- $121$
- $133$
- $143$
So you can simply:
- List all multiples of $6$
- List the two neighbors next to each one of them
- Memorize the ones mentioned above and eliminate them
UPDATE:
Just in order to clarify (and simplify) the method mentioned above.
All you have to do is to write down two lists, one starting from $7$ and the other starting from $11$.
Increment each list by $6$ until $150$, and eliminate the values that you have memorized in advance.
$\require{cancel}$
- $\small7,13,19,\color\red{\cancel{25}},31,37,43,\color\green{\cancel{49}},\color\red{\cancel{55}},61,67,73,79,\color\red{\cancel{85}},\color\green{\cancel{91}},97,103,109,\color\red{\cancel{115}},\color\green{\cancel{121}},127,\color\green{\cancel{133}},139,\color\red{\cancel{145}}$
- $\small11,17,23,29,\color\red{\cancel{35}},41,47,53,59,\color\red{\cancel{65}},71,\color\green{\cancel{77}},83,89,\color\red{\cancel{95}},101,107,113,\color\green{\cancel{119}},\color\red{\cancel{125}},131,137,\color\green{\cancel{143}},149$
Given a number $n$.
You need to (1) find all primes smaller than $\sqrt{n}$ and (2) see if any of them divides $n$.
If none of them divides $n$ then you have a prime, otherwise it's a composite number.
Example:
$\endgroup$ 4 $\begingroup$Is 147 prime? $\sqrt{147} < 13$ so we have 2, 3, 5, 7, and 11 to check.
3 divides 147 so we don't need to look further.
147 is a composite number.
My favorite mnemonic:
91 is the only number less than 100 that looks like a prime and isn't.
That's because these numbers don't look like primes: evens, multiples of 5, multiples of 3 (sum of digits tells you), 49, 77.
(This builds on @origimbo 's answer.)
$\endgroup$ 2 $\begingroup$Other answers cover things in far greater detail, but to expand on a comment by barak manos on their own answer, in terms of quick ways of testing and in order of speed of checking you can throw away:
- all even numbers
- all numbers whose digits end in five.
- all numbers whose digits add up to a multiple of three.
A couple of other small primes have more complicated tests, see for example here which covers 7 and 11.
$\endgroup$ 5 $\begingroup$I'd probably recommend just knowing all your primes between 7-150.
Start with 7 and count by 2s. If it looks prime, name it. The 3 exceptions between 1-100 are 57, 87 and 91. (I'm assuming "77" and "93" don't look prime to you.)
Keep counting past 100 and write your guesses down. Then check them all by Googling a list of prime numbers. Whichever ones you got wrong, memorize. This won't be many because you'll guess most right.
$\endgroup$ $\begingroup$Prime numbers greater than 3 are of the form $6n \pm 1$ , then you can test manually between 7 and 150. It will be easier than testing every odd integer as mentioned in other answer.
$\endgroup$ 0 $\begingroup$There is no answer yet which points this out: A couple of years ago it was found that you can test for primality in polynomial time. See
$\endgroup$ 1 $\begingroup$Start with the square root of 150, the integer value is 12. Your prime divisors are 2 3 5 7 and 11. Eliminate the even numbers and the numbers ending in 5. The first test will be 3 squared or 9 in this case add 6 to 9 and so on to eliminate the 3s. The next test is 7 squared or 49 and this time add 14 to eliminate the 7s. The last test is 11 squared or 121 and this time add 22 to eliminate the 11s. The numbers left on your list should be prime numbers. Or Make a chart with 2, 3, 7, 9 on the left side and 0, 10, 20, 30 ..... 140 across the top. This eliminates the even numbers and numbers ending in 5. Then it's 3*3 = 9, 3*7 = 21, 3*9 = 27, 11*3 = 33 etc. Then 7*7 = 49, 7*11 = 77, 7*13 = 91 etc. Then 11*11 = 121 and 11*13 = 143 and the remaining numbers are prime.
$\endgroup$
