Results 1 to 2 of 2

Math Help - program problem about primality test

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    36

    program problem about primality test

    the problem is, devise the most efficient algorithm to determine primality <1000000. show this by comparing the times taken by different algorithms.

    i made a trial division, fermat test, euler test, euler-jacobi test, miller rabin test.

    and i think a trial division + miller rabin will be the most efficient.
    so i ran my program < 100000 and timed it , it costs 20 sec.

    for miller rabin base 2 and base 3 , the time is 50 sec.

    BUT, for those other methods, their times are less than 5 sec.

    So how could trial division + miller rabin be the most efficient way?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by amberxinya View Post
    the problem is, devise the most efficient algorithm to determine primality <1000000. show this by comparing the times taken by different algorithms.

    i made a trial division, fermat test, euler test, euler-jacobi test, miller rabin test.

    and i think a trial division + miller rabin will be the most efficient.
    so i ran my program < 100000 and timed it , it costs 20 sec.

    for miller rabin base 2 and base 3 , the time is 50 sec.

    BUT, for those other methods, their times are less than 5 sec.

    So how could trial division + miller rabin be the most efficient way?
    Try trial division using a table of all primes <1000 (there are only 168 of them).

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The fastest way to test primality ?
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 9th 2011, 10:00 AM
  2. Wilson's Primality Test ... what ?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 9th 2010, 07:44 AM
  3. Ironing out the Lucas Primality Test proof
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: April 24th 2010, 07:31 PM
  4. Fixing The Program (Program Correctness)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 21st 2009, 03:17 PM
  5. The Miller-Rabin test for primality...
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 11th 2008, 03:24 PM

Search Tags


/mathhelpforum @mathhelpforum