Thread: 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!

Originally Posted by Greg98

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.