Are There Faster Methods to Determine Primes and Their Factors?

[LearningMath]

Hi all,

I'm reviewing some problems that involve finding the prime factors of composite numbers (e.g. prime factors of 44 are 2, 2, 11) and I had two questions about prime numbers and factors of composite numbers:

1) Is there some sort of quick test to tell if a number is prime? Or, does one have to run through every possible divisor in order to see?

For example, in one of my problems I came up with 269. I can't tell just by looking at it if this is prime or not. Do I t/f have to start dividing by 3, then try 9, and so on until I can truly say if it's prime or not?

Surely some smart person a couple thousand years figured out a faster way...

2) Related to question 1, is there a shortcut to finding the factors of any number - or does it all start and end with basic trial and error of various divisors?

Thanks in advance!

 

[lurflurf]

Basically factorizing integers is hard and some trial and error is needed. It can help if you know in advance what to look for. One could try some small factors, or if you know there are no small factors you can try some larger factors.

 

[Hurkyl]

Mental arithmetic is not really an important topic in mathematics -- it's more of a side show.

That said, I find it difficult to imagine a faster way to mentally test if 269 is prime than checking whether or not it's divisible by 2,3,5,7,11, or 13. Half of these are trivial calculations, and the other half very easy. (If you do mental arithmetic, you will surely have already memorized that 17²=289, and so you can stop after checking 13)

I have the same response with factoring.

I know someone who uses factorization[/url] to mentally factor numbers -- but unless the factorization was easy to spot, you generally wouldn't bother until you're dealing with much larger numbers, and you've already done trial division by the smallest primes.

 

[HallsofIvy]

The best way of determining whether a lot of different numbers are prime is to use a "sieve"- Write all integers including your list of numbers, mark out all evens, all multiples of 3, etc.

But the fastest way to determine whether a single number is prime or not is simply to try dividing by primes. Notice "dividing by primes". Once you have determined that 3 does not divide your number there is no point in trying "9", it can't possibly divide the number. One thing that "smart people" have determined is that you only need to try primes up to the square root of your number.

The square root of 269 is 16 point something so the largest prime you need to try is 13.Since 269 is not even, you don't need to try 2. 3 divides into 269 89 times with remainder 1 (more simply, 2+ 6+ 9= 17 and 1+ 7= 8 ("casting out nines") which is not divisible by 3). Since 269 does not end in 0 or 5 it is not divisible by 5. 7 divides into 269 38 point something so it is not divisible by 7. 11 divides into 269 24 point something times. 13 divides into 269 20 point something times. 6 divisions, 3 of which are "trivial" to show that 269 is a prime number.

 

[LearningMath]

These are all great responses. It looks like, for the most part, I'll be sticking to the trusty pencil and paper. That's an interesting point about square roots, though; hadn't thought of that. Thanks!