Results 1 to 2 of 2

Math Help - Simple primality testing algorithm

  1. #1
    Junior Member Greg98's Avatar
    Joined
    Oct 2009
    From
    Brugge, BEL
    Posts
    39

    Simple primality testing algorithm

    Hello,
    First sorry about plain ASCII - LaTeX is aching again. I was reading my data structures and algorithms textbook and came across with following na´ve primality testing algorithm:
    Code:
    PRIMALITYTEST(n)
    1  x <- GCD(n, 210)
    2  if x = 1 then return TRUE
    3     else return FALSE
    It was said that, if the 8 < n < 120, then algorithm doesn't fail at all. But if the n is chosen from[1, i], where i is "large", it fails about 1/2 * 2/3 * 4/5 * 6/7 (close to 23%) of the times. Question is, where does that probability come from? No other information was given, so I'm totally puzzled. Maybe that approximation follows from Prime number theorem or something. So, clarification is welcome. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Greg98 View Post
    Hello,
    First sorry about plain ASCII - LaTeX is aching again. I was reading my data structures and algorithms textbook and came across with following na´ve primality testing algorithm:
    Code:
    PRIMALITYTEST(n)
    1  x <- GCD(n, 210)
    2  if x = 1 then return TRUE
    3     else return FALSE
    It was said that, if the 8 < n < 120, then algorithm doesn't fail at all. But if the n is chosen from[1, i], where i is "large", it fails about 1/2 * 2/3 * 4/5 * 6/7 (close to 23%) of the times. Question is, where does that probability come from? No other information was given, so I'm totally puzzled. Maybe that approximation follows from Prime number theorem or something. So, clarification is welcome.
    The algorithm simply checks whether a number is divisible by 2, 3, 5 or 7. The proportion of numbers not of that form is 1/2 * 2/3 * 4/5 * 6/7. But the proportion of prime numbers is very much smaller than that (approximately 1/ln(n) in the region of a large number n, by the prime number theorem). So in nearly all the cases where n is not divisible by 2, 3, 5 or 7, the algorithm will return a false positive.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. testing simple hypothesis
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: April 18th 2011, 10:51 PM
  2. Help with testing an algorithm's accuracy
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 17th 2010, 05:32 AM
  3. Simultaneous integer primality testing
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: April 12th 2009, 06:40 PM
  4. [HELP]Relative Primality in the Following Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 28th 2008, 06:37 AM
  5. primality testing - ugh - HELP
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 16th 2007, 08:26 PM

Search Tags


/mathhelpforum @mathhelpforum