# Determine a number is prime or not

• Mar 7th 2010, 04:47 AM
ManuLi
Determine a number is prime or not
Hi,

I was aked to check whether 241 is prime or not. The time given was 40 sec. But I took a lot of time to determine this.

Is there any tricks avialble to quickly determine whether a number is prime or not?

Thanks!
• Mar 7th 2010, 05:00 AM
Prove It
Quote:

Originally Posted by ManuLi
Hi,

I was aked to check whether 241 is prime or not. The time given was 40 sec. But I took a lot of time to determine this.

Is there any tricks avialble to quickly determine whether a number is prime or not?

Thanks!

Have you heard of the divisibility tests?

Divisibility rule - Wikipedia, the free encyclopedia

Otherwise you can draw a factor tree:

Integer factorization - Wikipedia, the free encyclopedia

(see Prime Factorisation).
• Mar 7th 2010, 12:18 PM
Moo
Hello,

First, see roughly that 15²=225, so if a prime number divides 241, it must be less than 16.
Immediate known rules exclude 2 (and hence any even number), 5, 3 & 9 (sum of numbers), 11 (we know that 21*11=231)
now there remain 7 and 13, that's all...

7*10=70, 7*30=210. So is 241-210=31 divisible by 7 ? No. So 7 doesn't divide 241.

13*20=260. So is 260-241=19 divisible by 13 ? No. So 13 doesn't divide 13.

So 241 is a prime number

(took me less than 30 sec to find it out, so it's feasible)
• Mar 7th 2010, 12:50 PM
arcketer
An important thing to know, as Moo mentioned, is some basics about what numbers divide a numbers. The rule with summing the digits for 3 and 9 are important, as well as understanding why one can eliminate 2, 5, 10 and 11.