To try to simulate the Sieve of Eratosthenes, Siv builds a machine with the goal of...

Transcribed Image Text:

To try to simulate the Sieve of Eratosthenes, Siv builds a machine with the goal of finding all the primes less than 10,000. Each of the integers from 2 to 10,000 has a lamp displaying that integer, that can be turned ON or OFF. The machine begins with all lamps turned ON. In the first pass of the machine, the lamps for all multiples of 2 are turned OFF, except for 2 itself. In the second pass, the lamps for all multiples of 3 change state, except for 3 itself. The machine then does a pass for each successive prime p that is less than 100, changing the state of all lamps that are multiples of p, except for p itself. Note: "Changing state" means that a lamp that was ON changes to OFF, and a lamp that was OFF changes to ON. Let m be the maximum number of times that any lamp in the machine changes state from ON to OFF. Determine with justification the value of m, and an integer whose lamp gets turned OFF m times. Prove that the machine has no lamp that turns OFF more than m times. To try to simulate the Sieve of Eratosthenes, Siv builds a machine with the goal of finding all the primes less than 10,000. Each of the integers from 2 to 10,000 has a lamp displaying that integer, that can be turned ON or OFF. The machine begins with all lamps turned ON. In the first pass of the machine, the lamps for all multiples of 2 are turned OFF, except for 2 itself. In the second pass, the lamps for all multiples of 3 change state, except for 3 itself. The machine then does a pass for each successive prime p that is less than 100, changing the state of all lamps that are multiples of p, except for p itself. Note: "Changing state" means that a lamp that was ON changes to OFF, and a lamp that was OFF changes to ON. Let m be the maximum number of times that any lamp in the machine changes state from ON to OFF. Determine with justification the value of m, and an integer whose lamp gets turned OFF m times. Prove that the machine has no lamp that turns OFF more than m times.