Discrete Mathmatics Contradiction & Contraposition

Question

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 = 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?

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?

YesNo     

Is n prime?

YesNo     

(c)

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?

YesNo     

Is n prime?

YesNo     

(d)

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?

YesNo     

Is n prime?

YesNo     

Answer 1

8381 is not prime, as it is divisible by 17

9,867 can be divided by 3 as its digits SUM to 30, a multiple of 3. So it is not prime either.

the other two numbers are prime

I have uploaded a document which executes the algorithm you have described in VBA.

You must RENAME this document with the *.docm filename extension so as to enable

the macros to run the script.

The file is TestPrimeNumber.doc under this link. Otherwise, there are PLENTY of online

calculators that will do it for you.

Simply google Prime number calculator.