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.
1) Let n = 8,381.
How many prime numbers are less than or equal to the square root of n?
Is n divisible by any of these numbers?
A) Yes
B) No
Is n prime?
A) Yes
B) No
2) 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?
A) Yes
B) No
Is n prime?
A) Yes
B) No
3) Let n = 8,629.
How many prime numbers are less than or equal to the square root of n?
Is n divisible by any of these numbers?
A) Yes
B) No
Is n prime?
A) Yes
B) No
4) Let n = 9,867.
How many prime numbers are less than or equal to the square root of n?
Is n divisible by any of these numbers?
A) Yes
B) No
Is n prime?
A) Yes
B) No