Thread: 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!

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).

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)

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.