Andrew and Bob are writing a computer program which gives the prime factorization of a number.
Andrew suggests the following structure for the program:
∙ User selects an integer, x 0 ∙ The integer is divided by an integer, y , in ascending order starting from 2 until x 0 = 0 m o d y at which point the program prints y and we find x 1 = y x 0 . ∙ We repeat the instructions above using x 1 instead of x 0 and upon each iteration finding x n = y x n − 1 . ∙ The program stops executing when x n is itself prime.
For example,
Let, x 0 = 2 0
2 0 = 0 m o d 2 ∴ x 1 = 2 2 0 = 1 0
Repeating for x 1 ,
1 0 = 0 m o d 2 ∴ x 2 = 2 1 0 = 5
Since x 2 is prime the program stops executing. It has printed out 2 0 = 2 × 2 × 5 .
Bob suggests that for some integers, the program would not work as y would not be prime and so the program would not give the correct factorization.
Is Bob correct?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Problem Loading...
Note Loading...
Set Loading...
If at some point, x n can be divided by a p , where a > 1 and p ≥ 2 is prime, then we will never check this because division by p will be checked first.