Q1: An integer N>1 is called prime number if its only positive divisor are 1 and n; otherwise, n is called a composite number. For example, the following are the positive numbers less than 20:

2, 3, 5,7,11,13,17,19

If N>1 is not prime i.e. if n is composite then n must have a divisor K1 such that Kn or, in other words, K₂ n...

Suppose we want to find all the prime number less than given number m such as 30. This can be done by Sieve Method which consists of the following steps

First list the 30 numbers

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,22,23,24,25,26,27,28,29,30

Cross out 1 and multiple of 2 from the list as follows:

2,3,5,7,9,11,13,17,19,21,23,25,27,29

Since 3 is the first number following 2 that has not been eliminated, cross out the multiple of 3 from the list as follows

2,3,5,7,11,13,17,19,23,25,29

Since 5 is the first number following 3 that has not been eliminated, cross out the multiple of 5 from the list as follows

2,3,5,7,11,13,17,19,23,29

Now 7 is the first number following 5 that has not been eliminated, but 7² > 30. This means the algorithm is finished and the numbers left in the list are primes less than 30

2,3,5,7,11,13,17,19,23,29

Translate the sieve Method into an algorithm to find all prime numbers less than given number n. Analyze the algorithm for time complexity.

Q1: An integer N>1 is called prime number if its only positive divisor are 1 and n; otherwise, n is called a composite number. For example, the following are the positive numbers less than 20:

2, 3, 5,7,11,13,17,19

If N>1 is not prime i.e. if n is composite then n must have a divisor K1 such that Kn or, in other words, K₂ n...

Suppose we want to find all the prime number less than given number m such as 30. This can be done by Sieve Method which consists of the following steps

First list the 30 numbers

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,22,23,24,25,26,27,28,29,30

Cross out 1 and multiple of 2 from the list as follows:

2,3,5,7,9,11,13,17,19,21,23,25,27,29

Since 3 is the first number following 2 that has not been eliminated, cross out the multiple of 3 from the list as follows

2,3,5,7,11,13,17,19,23,25,29

Since 5 is the first number following 3 that has not been eliminated, cross out the multiple of 5 from the list as follows

2,3,5,7,11,13,17,19,23,29

Now 7 is the first number following 5 that has not been eliminated, but 7² > 30. This means the algorithm is finished and the numbers left in the list are primes less than 30

2,3,5,7,11,13,17,19,23,29

Translate the sieve Method into an algorithm to find all prime numbers less than given number n. Analyze the algorithm for time complexity.