1. The Sieve of Eratosthenes is a method of finding all prime numbers up to some

Question

1. The Sieve of Eratosthenes is a method of finding all prime numbers up to some fixed upper limit. It operates in the following way: (a). Create an array of boolean values all initialized to true. As the algorithm progresses, array elements with prime subscripts will remain true, while all other array locations will end up with false values. (b) Starting with array location 2, if a particular location contains true, then loop through the remainder of the array and set to false each location whose subscript is a multiple of the element which is true. So, since location 2 is true, you loop through all multiples of 2, setting those locations to false. Next, since location 3 is also still true, loop through the rest of the array marking every position that is a multiple of 3 to false. Continue this process until you have reached the square root of the array size. Use the Sieve of Eratosthenes to determine how many prime numbers there are that are less than one million. NOTES: this is being done in jGRASP.

Explanation / Answer

public class PrimeSieve { public static void main(String[] args) { int N = Integer.parseInt(args[0]); // initially assume all integers are prime boolean[] isPrime = new boolean[N + 1]; for (int i = 2; i

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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