Write an algorithm to check if is prime.
(Hint: A prime number has exactly two distinct factors, 1 and . Can you make use of to write out ?)
Confirming your payment
The World of Algorithms · Question 13 of 15
Write an algorithm to check if is prime.
(Hint: A prime number has exactly two distinct factors, 1 and . Can you make use of to write out ?)
Algorithm prime(n)
Let divisors-of-n be the list obtained by computing divisors(n).
Count the number of elements in divisors-of-n.
If the count is exactly 2, report " is prime". Otherwise, report " is not prime".
This is correct because a prime has exactly two distinct divisors, 1 and itself. The number 1 has only one divisor, and a composite number has at least three, so both are correctly reported as not prime.
Executing the algorithm:
prime(13): divisors(13) = [1, 13] has 2 elements, so 13 is prime.
prime(15): divisors(15) = [1, 3, 5, 15] has 4 elements, so 15 is not prime.
prime(1): divisors(1) = [1] has 1 element, so 1 is not prime.
A faster version (we do not need the whole list): if , report "not prime". Otherwise, for each from 2 to , if divides , report "not prime" and stop. If no such is found, report "prime". For prime(15) this stops at after 2 checks.