A prime number is an integer that is greater than 1 that is evenly divisible onl

Question

A prime number is an integer that is greater than 1 that is evenly divisible only by itself
and 1. For example, 2, 3, 5, and 11 are prime numbers, but 4, 9, and 22 are not.
The Sieve of Eratosthenes is an ancient and extremely simple way to identify all of the
prime numbers less than a given value n. The sieve works as follows:
1. Start by listing all of the integers from 2 through n.
2. Begin with 2 and cross out (eliminate, or mark) all integers that are greater than 2 that
are multiples of 2 (for example, eliminate 4, 6, 8, 10, etc.).
3. Find the next unmarked integer and remove all of its multiples from the list (except for
the number itself). For example, the ?rst unmarked integer after 2 is 3, so we remove
or mark all of the unmarked multiples of 3 that are greater than 3 (6, 9, 12, etc.).
4. Repeat this multiple-marking process for each next unmarked number in turn, until we
reach the end of the list.
5. At the end of this process, all of the remaining unmarked numbers are prime; the
marked numbers are composite (non-prime) values.
For example, here is an example using the sieve algorithm to ?nd all prime integers less
than 30 (marked numbers are replaced by an X):2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
2 3 X 5 X 7 X 9 X 11 X 13 X 15 X 17 X 19 X 21 X 23 X 25 X 27 X 29 X (mark 2s)
2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X 25 X X X 29 X (mark 3s)
2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X (mark 5s)
2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X (mark 7s)
2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X (mark 11s)
2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19 X X X 23 X X X X X 29 X (mark 13s)
etc.
(Note that, as a shortcut, you can stop marking once you have passed n/2)
Complete the sieve() method. This method takes an integer value n as its argument,
where 2 = n = 500), and returns an ArrayList containing all of the prime numbers
between 2 and n, inclusive, in ascending order.

Explanation / Answer

public static ArrayList<Integer> sieve(int n)
{
      // create starting list
      ArrayList<Integer> list = new ArrayList<Integer();
      for(int i = 2; i <= n; i++)
      {
            list.add(i);
      }
      // start removing numbers
      int loc = 0;
      while(loc < list.size())
      {
            // remove multiples of number at loc
            int prime = list.get(loc++);
            int stop = list.get(list.size()-1);
           
            for(int i = 2; i*prime <= stop; i++)
            {
                  list.remove(i*prime);
            }
            // continue with next number
      }

      return list;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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