Question

Scenario

Implementing the sieve of Eratosthenes algorithm to find all prime numbers up to a given limit.

Aim

Develop code for implementing the sieve of Eratosthenes.

Steps for Completion

1. Implement the isPrime() method of the SieveOfEratosthenes class that should return true if the number is prime, and false otherwise.

2. Consider building the sieve in the class constructor.

CODE GIVEN

public class SieveOfEratosthenes {

public SieveOfEratosthenes(int maxValue) {

// Build the sieve here

}

public boolean isPrime(int value) {

// Write your code here

}

}

Answer 1

ANS) /run the program on local machine main method is not created in this as implementaion of functions is required/

public class SieveOfEratosthenes {

public SieveOfEratosthenes(int maxValue) {

  

// Build the sieve here

  

boolean prime[] = new boolean[maxValue + 1];

for(int i=0;i<maxValue;i++)

prime[i] = true;

for(int p = 2; p*p <=maxValue; p++)

{

// If number is not changed, then it is a prime

if (prime[p] == true) {

// Update all multiples of p

for (int i = p * p; i <= maxValue; i += p)

prime[i] = false;

}

}

for(int i = 2; i <= maxValue; i++)

{

if(prime[i] == true)

System.out.print(i + " ");

}

}

public boolean isPrime(int value) {

// Write your code here

boolean flag = false;

for(int i = 2; i <= value/2; ++i)

{

// condition for nonprime number

if(value % i == 0)

{

flag = true;

break;

}

}

if (flag == false) {

return true;

}

else {

return false;

}

}

}