Prime Numbers and the Sieve of Erastothenes Using the Sieve of Erastothenes calc

Question

Prime Numbers and the Sieve of Erastothenes Using the Sieve of Erastothenes calculate the prime numbers from 2 to 200 The Sieve of Erastothenes is an ancient algorithm that generates prime numbers. Consider the list of numbers from 2 to 10 as follows: (NOTE YOUR requirement is to calculate primes from 2 to 200 using this technique) The algorithm starts with the first prime number in the list, which is 2, and then iterates through the remainder of the list, removing any number that is a multiple of 2 (in this case, 4, 6, 8. and 10), leaving We then repeat the process with the second prime number in the list, which is 3, and then iterate through the remainder of the list, removing any number that is a multiple of 3 (in this case 9), leaving We then repeat starting with each successive prime number. When your program finishes, the numbers that remain in the list are all prime numbers. Implement this algorithm using an ArrayList of integers that is initialized to the values from 2 to 200. OUTPUT requirements - Output all intermediate steps and final list of primes: 2 3 4 5 6 7 8 9 10 11 12 ... 200 (all numbers, 2-200 in a row) 2 3 5 7 9 11 13 15 ... 199 (list with all multiples of second element (2) removed) 2 3 5 7 9 11 13 17 ... 199 (list with all multiples of third remaining element (5) element removed) ... (continue to output successive rows) Last line should read Prime Numbers = 2 3 5 7 .... (up to 199 showing all prime numbers)

Explanation / Answer

import java.util.*;

public class PrimeUsingSieveErasthothenes
{
public static void main(String a[])
{
ArrayList list = new ArrayList();
Scanner sc = new Scanner(System.in);
System.out.println("Enter limit");
int item, d,s;
int n = sc.nextInt();
  
  
// Intialize the list with values
for(int i=2;i<=n;i++)
list.add(i);
  
System.out.println("Original List "+list);
  
// remove all elements which are multiple of each element in the list
for(int i=0; i<list.size();i++)
{
d=(int)list.get(i);
for(int j=i+1; j<list.size();j++)
{
item=(int)list.get(j);
if(item%d==0)
list.remove(j);
}
System.out.println("List with all elements multiple of "+d+" removed "+list);
}
  
System.out.println("Prime Numbers: "+list);
  
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.