Thread: Determine a number is prime or not

1. 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!

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

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

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