simpler way to find if a number is prime? random inquiry

[furyshade]

i just had a blackout for last 24+ hours, got really bored, started wondering if there was a better way to see if a number was prime than dividing a number by all primes below half of the original number

[godBoy]

You will find them quicker if you start from two and go up.

The first step is to see if it's divisible by two - even numbers are out.
Then see if it's divisible by three etc..

I don't know of a quicker method but starting from two and working upwards would knock out non-primes the fastest.

[Siegmund]

You only have to go as far as the square root of the number, not half the number.

Aside from that, you can concentrate on the most efficient ways of testing divisibility, and for numbers of special form (like a*b^c+1) there are other, faster, tests. But no, there is not any magical fast way to test any number.

If its a topic you'd like to pursue in some depth, http://primes.utm.edu is a good place to start reading.

[pokerbobo]

There are a few tricks to see if numbers are divisible by other numbers

all even numbers are out as stated earlier

numbers divisible by three you can add all digits in a number ie 213 is 2+1+3=6....if the sum is divisible by 3 then the full number is divisible by 3.

4 is even so it doest matter...but if the last two digits are divisible by 4, then the entire number is divisible by 4.

5 Obviously all numbers ending in 5 or 0 are div by 5

6 and 8 again both even

9 works the same as 3

That just leaves 7 to screw things up.

[furyshade]

yeah, im talking more complex, like 391 is a mutliple of 17 and 23, so those rules wont work

[Neuge]

http://mathworld.wolfram.com/NumberFieldSieve.html

[FortunaMaximus]

[ QUOTE ]
yeah, im talking more complex, like 391 is a mutliple of 17 and 23, so those rules wont work

[/ QUOTE ]

Well, you know the square root of 391 is under 20. So I assume you can memorize a table of primes till 101. Divide number by primes till you get a match or the number's divisible.

With practice, it's a decent mental sieve to break down most larger numbers into their primes. Good mental gymnastics too.

[m_the0ry]

Someone already mentioned number feild sieve. Sieve of Eratosthenes is also really easy to program in any basic scripting language. Check out the wikipedia entry it even has C++ code you can implement to do it.

[GMontag]

Fermat's Little Theorem FTW.

a^p = a mod p holds for all integers a and any prime p.

However, there are some "psuedoprimes", numbers which are composite, but which the above equation is still true for one or more integers a. So finding that the equation holds doesn't prove p is prime, but it does make it more likely, especially if it holds for several different integers a.

[wooly_chicken]

[ QUOTE ]
There are a few tricks to see if numbers are divisible by other numbers

all even numbers are out as stated earlier

numbers divisible by three you can add all digits in a number ie 213 is 2+1+3=6....if the sum is divisible by 3 then the full number is divisible by 3.

4 is even so it doest matter...but if the last two digits are divisible by 4, then the entire number is divisible by 4.

5 Obviously all numbers ending in 5 or 0 are div by 5

6 and 8 again both even

9 works the same as 3

That just leaves 7 to screw things up.

[/ QUOTE ]

Multiply the last digit of a number by five and add what you get to the remaining digits. What you get is divisible by 7 iff what you started with was. For example:

1547 is divisible by 7 iff 154+35=189 is divisible by 7 iff 18+5*9=63 is divisible by 7 iff 6+5*3=21 is divisible by 7 iff 2+5*1=7 is divisible by 7.

You can come up with similar tests for any number (the key idea for 7 is that 5 is the multiplicative inverse of 10 in $\Z/7\Z$), but they don't seem particularly useful to me.

EDIT: I suppose it would be easier to use -2 instead of 5.