# Finding if a Number is Prime

• Nov 18th 2006, 01:34 PM
Quick
Finding if a Number is Prime
I was wondering if there was some way to determine if a number is prime without testing every number below it to see if it has a divisor.

Such as, I found that all primes can be expressed in the form: $6k\pm1$ (except for 2 and 3) but not all numbers that can be expressed in $6k\pm1$ are prime.

Is there something that shows definitively that a number is prime?
• Nov 18th 2006, 01:42 PM
Aglaia
if I do not mistake if you can write that number in this way that means that it must be prime: p=2^(n)+1 with n power of 2
• Nov 18th 2006, 01:58 PM
CaptainBlack
Quote:

Originally Posted by Quick
I was wondering if there was some way to determine if a number is prime without testing every number below it to see if it has a divisor.

Such as, I found that all primes can be expressed in the form: $6k\pm1$ (except for 2 and 3) but not all numbers that can be expressed in $6k\pm1$ are prime.

Is there something that shows definitively that a number is prime?

If a number N is composite then at least one factor is <=sqrt(N).
So at most you need test sqrt(N) candidate divisors to determine
if N is prime.

If you maintain a list of primes, then you only need test for prime
divisors <sqrt(N), of which there are ~2 sqrt(N)/ln(N).

And I'm sure that there are other techniques that will
reduce the amount of work further.

RonL
• Nov 18th 2006, 02:08 PM
ThePerfectHacker
Quote:

Originally Posted by Quick
I was wondering if there was some way to determine if a number is prime without testing every number below it to see if it has a divisor.

Such as, I found that all primes can be expressed in the form: $6k\pm1$ (except for 2 and 3) but not all numbers that can be expressed in $6k\pm1$ are prime.

Is there something that shows definitively that a number is prime?

The question is not whether there is a way, it is how efficient is the technique.

For example, can you find $100!$ certainly but it is a mess.

So what you are asking whether there is a necessary and sufficent condition to determine whether a number is prime and there is one. It is called Wilson's theorem.
Here is my version of it,

If,
$\left[ \frac{(p-1)!+1}{p} \right]=\frac{(p-1)!+1}{p}$
The $[\,\, ]$ means greatest integer function, that is, droping the decimal point.

(So more formally I am trying to say that the sequence,
$a_n=\left[ \frac{(p-1)!+1}{p} \right]$ is a prime for $n=p$ if and only if it is indepodent).

Problem is factorials are complicated to find even for computers (and sometimes even for me!).
---
What I am about to say I might be wrong so do not rely on it so much.
---
What you want is an algorithm that is efficient (my version of Wilson's theorem is not). Usually algorithms that run in logarithmic time are efficient (logarithmic times means the number of steps for a computer to compute is $\ln n$). Those are extremely efficient. Exponential time is horrific. But number theoresits found ways for primality test, i.e. to determine whether a number is prime or not efficiently in polynomial time. There is an unanswered question today (1,000,000 dollars) is called P versus NP. It says the class of problems that run in polynomial time is disjoint from the classs of problems that run in non-deterministic polynomial time (i.e. exponential time). That means since we have a certain method of primality testing
in polynomial time we can do no better by this conjecture :( . Meaning since we have an algorithm in polynomial time we cannot improve it to logarithmic time, which is why it takes computers (and even me sometimes) to crack a number into primes. (Careful I might be completely wrong on what I said).
---

I can show you some classic tests for smaller numbers.