Construct a sieve of Eratosthenes for the numbers from 2 to 100. (Write all the integers from 2 to 100. Cross out all multiples of 2 except 2 itself, then all the multiples of 3 except 3 itself, then all multiples of 5 except 5 itself, and so forth. Continue crossing out multiples of each successive prime number up to 100. The numbers that are not crossed out are the prime numbers from 2 to 100.) Use the test for primality and your sieve of Eratosthenes to determine whether the following numbers are prime Test for Primality Given an integer n > 1, to test whether n is prime check to see if it is divisible by a prime number less than or equal to its square root. If it is not divisible by any of these numbers, then it is prime. (a) Let n = 5,491. How many prime numbers are less than or equal to the square root of n? Is n divisible by any of these numbers? Yes
No
Is n prime?
Yes
No
(b) Let n = 9,157 How many prime numbers are less than or equal to the square root of n? Is n divisible by any of these numbers?
Yes
No
Is n prime?
Yes
Nο
(c) Let n = 8,627. How many prime numbers are less than or equal to the square root of n? Is n divisible by any of these numbers?
Yes
No
Is n prime?
Yes
No
(d) Let n = 7,161. How many prime numbers are less than or equal to the square root of n? Is n divisible by any of these numbers?
Yes
No
Is n prime?
Yes
No