21
$\begingroup$

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$
8
34
$\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:

enter image description here

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
  • 12
    $\begingroup$ Note that you're done with the sieve when you reach the square root of the range, in this case $\sqrt{150} \approx~ 12$. $\endgroup$ – Daniel R. Collins Feb 29 '16 at 14:15
  • $\begingroup$ @RemcoGerlich He is correct (actually you want to test to $\left \lceil{\sqrt{x}}\right \rceil $). See this question: stackoverflow.com/questions/5811151/… $\endgroup$ – Carser Mar 1 '16 at 13:05
  • 2
    $\begingroup$ @Jedediyah I assume you mean $\lfloor \sqrt{x} \rfloor$. $\endgroup$ – Travis Willse Mar 1 '16 at 13:07
  • $\begingroup$ @Travis Good assumption! ;p $\endgroup$ – Carser Mar 1 '16 at 13:07
  • $\begingroup$ @RemcoGerlich The animation actually does stop finding composite numbers at 11. You can see that after that test all of the remaining numbers are primes, and don't have any multiples that aren't already colored in. $\endgroup$ – Carser Mar 1 '16 at 13:11
12
$\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$
$\endgroup$
11
  • 5
    $\begingroup$ Yeah I definitely agree that if you know the range of numbers then it is easier to just memorize the primes in that interval. $\endgroup$ – Carser Feb 29 '16 at 12:47
  • $\begingroup$ @Jedediyah: Assuming that the range is small of course. $\endgroup$ – barak manos Feb 29 '16 at 12:48
  • $\begingroup$ @Jedediyah: And in the case above, you can just as well check the divisibility of each number in that range by $2,3,5,7,11$ (out of which, the first three are rather easy). $\endgroup$ – barak manos Feb 29 '16 at 12:49
  • 1
    $\begingroup$ For the range, doing the one away from a multiple of six you only need to check divisibility by 5,7,11 Five is obvious 11 almost obvious (there are only 13 of them and the single digit ones are obvious. With these tricks it shouldn't take more than a minute even with being very careful. $\endgroup$ – fleablood Feb 29 '16 at 16:55
  • 3
    $\begingroup$ @fleablood: 143 doesn't have smaller factors than 11 :-) I think the problem here is more or less what the questioner suggests in the question: rushing it under stress will cause mistakes, taking it slowly and methodically might take too long. As barak shows it's possible to prepare specifically to list primes up to 150 quickly (heck, you could just memorise the sequence of primes). But if you do that and then you're actually asked to list primes up to 160 quickly then your short-cuts may or may not still be valid. $\endgroup$ – Steve Jessop Mar 1 '16 at 11:36
7
$\begingroup$

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:

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.

$\endgroup$
4
  • 1
    $\begingroup$ The fact we are building on is that if $n$ is a composite then it has a prime factor smaller than $\sqrt{n}$. The proof is easy. $\endgroup$ – snoram Feb 29 '16 at 14:35
  • 4
    $\begingroup$ The would take an incredibly long time if you need to do it on every number between 7 and 150 and the OP already knows how to do that. S/he specifically asked for a method to avoid having to check every single number. $\endgroup$ – fleablood Feb 29 '16 at 16:50
  • $\begingroup$ Agreed it would take long time. But disagree that the question is clear on exactly what is being asked. It ends with two questions "Is there any way to test for prime numbers ? Or to prove whether that a number is a prime number ? " $\endgroup$ – snoram Mar 1 '16 at 7:10
  • $\begingroup$ My answer addresses both questions. $\endgroup$ – snoram Mar 1 '16 at 9:27
6
$\begingroup$

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
  • 1
    $\begingroup$ Comparing this with @barak manos's approach, I would say that 119 and 133 also fall in the "look like a prime but aren't" category going up to 150. For me at least, 121 and 143 are "obviously" multiples of 11, but it probably depends on the person. $\endgroup$ – Mario Carneiro Feb 29 '16 at 19:28
  • 6
    $\begingroup$ For some reason I always think 51 looks prime and 41 doesn't. Don't know why. Still that's a pretty cute statement. $\endgroup$ – fleablood Feb 29 '16 at 19:31
3
$\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
  • 2
    $\begingroup$ I'll never be able to remember the rule for division by 7 but "casting out" 7s is easy because 7 is a single digit. Given 840539438261 has the divisibility as 140539438261 which has the same as 539438261 as 119438261 as 49438261 as 438261 as 18261 as 4261 as 61 is not divisible by 7. You can do the same for any number but it's easiest for 7. It's the only way I know for 13. A number is divisible by 11 if the sum of the even place digits is the same as the odd placed digits or off by a multiple of 11. $\endgroup$ – fleablood Feb 29 '16 at 19:41
  • $\begingroup$ @fleablood: another test I learned for 7-divisibility is to subtract 21 times the least digit and then divide by 10. That is to say, discard the least digit and then subtract double the digit you discarded. Hence 840539438261 -> 84053943824 -> 8405394374 -> 840539429 -> 84053924 -> 8405384 -> 840530 > 84053 -> 8399 -> 821 -> 80 -> 8, so not divisible by 7. Note this doesn't tell you the modulus, whereas casting out does. You can do a similar trick for 17 using 51 in place of 21, and 13 using 39 (i.e. add 4 times the digit you chopped off). $\endgroup$ – Steve Jessop Mar 1 '16 at 11:49
  • $\begingroup$ @SteveJessop don't understand. 840539438261 to 84053943824. Okay, that's just subtracting 21 and dividing by 10. 84053943824 to 8405394374. Okay the 2 is the least digit so we remove it. Then... the eight before the 2 becomes a 7????? why? Then 8405394374 to 840539429 ... so the 374 gets turned into 29? WTF? $\endgroup$ – fleablood Mar 1 '16 at 17:04
  • $\begingroup$ @fleablood: by "least digit" I mean "least significant digit", sorry. 84053943824, chop off the last digit would be 8405394382. The last digit was 4, so subtracting 8 from 8405394382 leaves 8405394374. The net result is that we have subtracted 21 * 4 and then divided by 10, both of which operations preserve divisibility by 7. $\endgroup$ – Steve Jessop Mar 1 '16 at 17:07
  • $\begingroup$ Hmmm... in my opinion multiplying and carrying is just as hard as doing a complete division. Casting out is faster and easier. Especially as we have 142 other numbers to test. $\endgroup$ – fleablood Mar 1 '16 at 17:14
3
$\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$
2
$\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
1
$\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 https://en.wikipedia.org/wiki/AKS_primality_test

$\endgroup$
1
  • $\begingroup$ That's true, but given the OP is concerned with a 1-byte input, this breakthrough may not be terribly relevant :P $\endgroup$ – djechlin Mar 1 '16 at 15:07
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.