Determining Prime Numbers: Tips & Tricks

[Haunted Physt]

Hello,

This is my first post. Anyways, from the beginning, since I started learning the subjects at higher level, I have faced this problem -

How to determine if the nos. is a prime no. ?

The numbers under 100 are known to me, but if a bigger digit comes, are there any tricks to determining whether it is a prime no. or not? In one of my previous exams, I had found myself in trouble with just this small no. 151 ... and yeah, I found that it was prime within minutes, but I always try to divide the number by 7, 13, 17, and 19 to determine whether it is a prime or not. But this is just trial and error, so, could anybody, any mathgenius disclose me the trick? Require it badly for the upcoming exams - 1 day to go!

Currently I am in XIth Grade.

 

[genneth]

If you're in 11th grade, and you're doing this for an exam, stick to trial division. Remember that you only have to check up to the square root of the number. So even up to 200 you'd only have to try 2, 3, 5, 7, 11, 13, 17 and 19. Furthermore, you shouldn't have difficulty (i.e. takes only a few seconds) with 2, 3, 5. There is a trick with 11: http://www.jimloy.com/number/divis.htm For 7, 13, 17 and 19 you'll just have to stick to division. Nevertheless, it shouldn't take more a minute each (if you're taking longer, practise your division!)

In general, primality testing is one of those big number theory problems. In fact, if you're feeling up to it, learning about all the different methods will take you right to the forefront of number theory. However, all these methods are intended for numbers far bigger than you can (or want to) write down, and are suited for computers rather than humans.

 

[Haunted Physt]

The one of 11 is a really nice trick! Though, 7's rather a large trick. Aren't there any for the other numbers, 13, 17, and 19?

 

[genneth]

Not to my knowledge. Personally, I've never used the one for 7 -- it seems so much quicker to just divide.

 

[matt grime]

151 within minutes? Surely you mean within seconds: 2,3,5, clearly not. 7 doesn't divide 11, and hence doesn't divide 151. 11 doesn't divide it either, as we can see by the trick, or just thinking about it - 11 does divide 132 and not 19... And 13^2=169. If it took you more than 2 seconds, then this tells you not that you need more techniques, but that you just need to work on your mental arithmetic.

 

[CRGreathouse]

There's the 1001 trick as well, but that's really useful only for larger numbers. (1001 = 7 * 11 * 13, so subtracting 1001 leaves a number unchanged mod each of those, but it's easy to subtract multiples of 1001.)

 

[Haunted Physt]

151 within minutes? Surely you mean within seconds: 2,3,5, clearly not. 7 doesn't divide 11, and hence doesn't divide 151. 11 doesn't divide it either, as we can see by the trick, or just thinking about it - 11 does divide 132 and not 19... And 13^2=169. If it took you more than 2 seconds, then this tells you not that you need more techniques, but that you just need to work on your mental arithmetic.

Well, I actually meant within seconds, but you are true. So any tips to working on Mental Arithmatic? Its really weak if I see that way...my Maths is to be improved!

 

[symbolipoint]

Haunted Physt, you want the Sieve of Eratosthenes. Great and fundamental exercise for finding prime numbers. Try an internet search. Also, your elementary school textbooks in arithmetic should discuss this.

List numbers in rows of 10; go from 1 to 200 (or whatever upper limit you want).
Put X on 1; put circle around 2;
Put X on all multiples of 2, but not on 2 itself.
Come back to the lowest unmarked number and put circle around it;
Put X on all multiples of this number.
Come back to the lowest unmarked number and put circle around it;
Continue in this manner until all of the numbers are marked.

The circled numbers are the prime numbers; the numbers with X (except 1) are all "composite" numbers.

 

[symbolipoint]

...Actually when I said "list the numbers...", I meant rows like 1 to 10, 11 to 20, 21 to 30... like that. You want a chart, not simply a running list, but a chart with rows of ten elements long.