Results 1 to 4 of 4

Math Help - Finding if a Number is Prime

  1. #1
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Sep 2006
    Posts
    26
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Quick View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Quick View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 24th 2011, 12:23 PM
  2. Prime number sum
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 26th 2011, 04:42 PM
  3. Replies: 1
    Last Post: September 2nd 2009, 09:31 AM
  4. Prime number
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: September 6th 2008, 09:21 AM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 09:11 PM

Search Tags


/mathhelpforum @mathhelpforum