Do you need to know all of the factors of a number in order to determine if it is prime or composite?

@MATH

Question

Do you need to know all of the factors of a number in order to determine if it is prime or composite? 
       
@MATH

jamesj · Answer

No, if you find one factor (that isn't 1 or the number itself), that's sufficient.

For example

n = 123473456742357832458902

This number has a factor of 2, and now we can immediately say that n is composite.  We don't need to find all of the other factors.

anonymous · Answer

what abt a prime number?

jamesj · Answer

Testing whether a number is prime is a pain.  The simplest way to test whether a number n is prime is to check whether every integer up to $ \sqrt{n} $ is a factor.

For example, suppose n = 1001.  $ \sqrt{n} = 31.6385.. $ so we will need to check all the primes from 2 to 31.

jamesj · Answer

For example, does 2 divide 1001?  We write 2 | 1001.  No, because if it did, the last digit would be 0,2,4,6 or 8.

Next.  3 | 1001?  No, because if it did, the sum of the digits of 1001 would be divisible by 3.

Next 5 | 1001 ?  No, because if it did, the last digit would be 5 or 0

Next 7 | 1001 ? Yes.  1001 = 7 * 143.

Hence 1001 is not prime.

jamesj · Answer

If however we had kept on going and none of the primes between 2 and 31 divided 
n = 1001, then we could conclude 1001 was prime

anonymous · Answer

LOL HEHE

jamesj · Answer

lol.  Ah, trust me.  I used to lecture mathematics at university.

jamesj · Answer

No.  Read it again and internalize it.

jamesj · Answer

In my head, the explanation is about 1/2 sec long.  If you fully understand it, it'll be that long for you too.  I wrote it the way I did so you could understand it.  I hope you do.  Making it shorter will make it harder to understand, not easier.

jamesj · Answer

You understand it and rewrite it to whatever size you need.  I've got to move on.