Exercise 4: Prime Numbers- Sieve of Eratosthenes Consider the following method t
ID: 3873272 • Letter: E
Question
Exercise 4: Prime Numbers- Sieve of Eratosthenes Consider the following method to generate all prime numbers in the range 2 to N. Start with the first prime number 2. In the list of the integers 2,3.. ,N, eliminate all multiples of 2 (these cannot be prime). Move on to the next number that is still in the list, which is 3. Eliminate all multiples of 3, i.e 9,15,21,... noting that 6,12,18,... have already been eliminated in the first step. Move on to the next number still in the list (which is 5) and eliminate its multiples. Continue until all multiples of the prime:s up to N have been eliminated, leaving only primes in the list. This is an ancient algorithm called the Sieve of Eratosthenes. Use this algorithm to implement the following Java method that returns an array of all primes in the range 2 to N. public static int[] primes (int N) f... ) For this algorithm, if you wish, you may use the following code to dynamically extend an array holding the primes found so far: prime sArray . Arrays. copyprime sArray, prinesArray.length + 1); You will need to import java.util.Arrays. The algorithm can be implemented in 12 Java statements (or less)Explanation / Answer
Answer:
class Sol
{
void Sol(int num)
{
boolean pri[] = new boolean[num+1]; //create a boolean array of size num to hold the status for prime number
for(int j=0;j<num;j++)
pri[j] = true; //make true to all
for(int i = 2; i*i <=num; i++)
{
if(pri[i] == true)
{
//element all non prime y making false in array
for(int k = i*2; k<= num; k += i)
pri[k] = false;
}
}
//Display prime
for(int h = 2; h<= num; h++)
{
if(pri[h] == true)
System.out.print(h + " ");
}
}
public static void main(String args[])
{
int n = 40;
Sol obj = new Sol();
obj.Sol(n);
}
}
Output:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.