Data Structure and Algorithm

Question

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 K≠1 such that K≤√n 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.

Answer 1

The algorithm is of polynomial order...

O (n^k) where k is the # of primes...

Not very efficient...

It is much more efficient just to look for divisors between 2 and sqrt(x)

-------------------------------------------------------------------------------------------

import java.math.*;

class PrimeNumber

{

// returns the first integer divisor of x that is less than sqrt(x), or -1 if prime

public long IsPrime( long x)

{

long iReturn = -1;

if (x==2) { iReturn=-1; }

else if (x==3) { iReturn=-1; }

else if (x==4) { iReturn=2; }

else if (x==5) { iReturn=-1; }

else if (x==6) { iReturn=2; }

else

{

long iStop = (long)(Math.ceil(Math.sqrt(x))+1);

for (long iLoop=2; iLoop< iStop; iLoop++)

{

if ((x % iLoop)==0)

{

iReturn = iLoop;

break;

}

}

}

return(iReturn);

}

public static void main(String args[])

{

int N=50;

if (args.length>0)

{

N = Integer.parseInt(args[0]);

}

PrimeNumber myPrime = new PrimeNumber();

for (int iLoop=2; iLoop<N; iLoop++)

{

if (myPrime.IsPrime(iLoop) == -1)

{

System.out.println(iLoop);

}

}

}

}