Lesson 5B: An Array Example


Let’s look at an example using an array to print all the prime numbers up to a given number.

What is a Prime Number?

  • A Prime Number, N, is a number that can only be divided evenly by the numbers 1 and itself (N).

Examples of Prime numbers: 2, 3, 5, 7, 11, 13, 17…

We can use a brute force method to calculate the Prime Numbers by using modulo division from 2 to N/2.

A far more efficient method is to use the technique of Eratosthenes – Sieve of Eratosthenes.

 

Eratosthenes Algorithm for Prime Numbers is as follows:

  1. Write down all the natural numbers from “2” to infinity (or a given limit)
  2. “Sieve out” every second number after “2” (or multiples of “2”).
  3. Move to the next available number that has not been “sieved out” (“3” in this case).
  4. “Sieve out” every multiple of that number.
  5. Go to the next available number and continue the process (go back to step [3]).

Eratosthenes

YouTube video of “The Sieve of Eratosthenes” from Region 10 Education Center.

You can already see that the Sieve of Eratosthenes is structured like an array. An array can be used to store a value that tells us if that element in the above table is Prime.

 

In-class exercise:

Create a Java program called “Prime.java” that takes two integer values as command line arguments. The first argument will be used to indicate which method to use to generate the Prime Numbers (“1” for Brute Force, and “2” for Sieve of Eratosthenes).

The second argument will be used to as the end number of the Prime Number list.

Use comments in your code!

public class Prime {
  public static void main(String[] args) {
    // Get the parameters from the command line
    int type = Integer.parseInt(args[0]);
    int N = Integer.parseInt(args[1]);

    if (type == 1) {
      // Brute force method code here
      // Hint: You need to use two nested for loops
    } else if (type == 2) {
      // Sieve of Eratosthenes code here
      // Hint: You can create an array of type Boolean
    }
  }
}

 

Extension of in-class exercise:

Re-write the Prime.java code to create two methods with an integer as parameter to the method.

  1. calcualtePrime1(int end)
  2. calculatePrime2(int end)
public class Prime {
  public static void main(String[] args) {
    // Get the parameters from the command line
    int type = Integer.parseInt(args[0]);
    int N = Integer.parseInt(args[1]);

    if (type == 1) {
      calculatePrime1(N);
    } else if (type == 2) {
      calculatePrime2(N);
    }
  }

  static void calculatePrime1(int end) {
    // Brute force method code here
    return;
  }

  static void calculatePrime2(int end) {
    // Sieve of Eratosthenes code here
    return;
  }
}