Create a list of integers from 2 to n (e.g. 2, 3, 4, ..., n) For integers p in t

Question

Create a list of integers from 2 to n (e.g. 2, 3, 4, ..., n) For integers p in the range [2, n/2], do the following: (a) If p is crossed off, skip the following step (b) Otherwise, cross off all multiples of p in the list not including p itself some of these numbers may already be crossed off and that's okay (e.g. 2p, 3p, 4p, ellipsis) Each number in the list that wasn't crossed off is prime For example, if we run this algorithm on n = 10, we get the following steps: At the end of this algorithm the numbers 2, 3, 5, and 7 are prime. You should implement this method using an Array List of Integers. You can simulate crossing out a number from the list by removing that element from the list. Be aware that ArrayList implements two different remove methods. remove(int) will remove an element at the index specified by the argument, and remove (Integer) will remove the first element equal to the object specified by the argument. Be careful which one you are calling! You are also responsible for writing a driver which will match the following sample output. Enter n: 15 Initial: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] Pass #1: [2, 3, 5, 7, 9, 11, 13, 15] Pass #2: [2, 3, 5, 7, 11, 13] Pass #3: [2, 3, 5, 7, 11, 13] Pass #4: [2, 3, 5, 7, 11, 13] Pass #5: [2, 3, 5, 7, 11, 13] Pass #6: [2, 3, 5, 7, 11, 13] Final: [2, 3, 5, 7, 11, 13]

Explanation / Answer

Sieve.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Sieve {

// Give string representation of list
public static String getStringForList(List<Integer> list)
{
StringBuilder sb = new StringBuilder();
sb.append("[" + list.get(0));
for(int i = 1; i < list.size(); i++)
{
sb.append(", " + list.get(i));
}
sb.append("]");
return sb.toString();
}
public static void main(String[] args)
{
// Declare list
List<Integer> primeList = new ArrayList<>();
Scanner sc = new Scanner(System.in);
  
// Tke user input
System.out.print("Enter n: ");
int n = sc.nextInt();
sc.close();
  
// fill initial list
for(int i = 2; i <= n; i++)
{
primeList.add(i);
}
  
// print initial value
System.out.println("Initial: " + getStringForList(primeList));
  
// Remove multiples and print pass result
for (int i = 2; i <= n/2; i++)
{
for (int j = 2; j*i <= n; j++)
{
Integer tobeRemoved = new Integer(i*j);
primeList.remove(tobeRemoved);
}
System.out.println("Pass #" + (i-1) + ": " + getStringForList(primeList));
}
  
// print final list
System.out.println("Final: " + getStringForList(primeList));
}
}

Sample output

Enter n: 15
Initial: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
Pass #1: [2, 3, 5, 7, 9, 11, 13, 15]
Pass #2: [2, 3, 5, 7, 11, 13]
Pass #3: [2, 3, 5, 7, 11, 13]
Pass #4: [2, 3, 5, 7, 11, 13]
Pass #5: [2, 3, 5, 7, 11, 13]
Pass #6: [2, 3, 5, 7, 11, 13]
Final: [2, 3, 5, 7, 11, 13]

Please rate positively is this solved your question. Comment if something is not clear.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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