Prime Directive project - solution

Hi.

Here’s my take on Prime Directive project. I made a couple of changes which significantly increased performance of the program by cutting time needed to perform calculations by half:

To illustrate how this may matter I used my own test array with very large integers:

int[] numbers = { 989898989, 989898987, 989898989, 989898987, 989898989, 989898987, 989898989, 989898987, 989898989 };

My original isPrime() method (and the result of following instructions) looked like this:

public boolean isPrime(int number) {
      for (int i = 2; i <= number - 1; i++) {
      if (number < 2 || number % i == 0) {
        return false;
      }
    }
    return true;
  }

Result - 25.531 seconds

[Running] cd "/Users/jankes_mj/Documents/Coding/Codecademy Projects/Java/Prime Directive/" && javac PrimeDirective.java && java PrimeDirective
[989898989, 989898989, 989898989, 989898989, 989898989]

[Done] exited with code=0 in **25.531 seconds**

I realised that there is no point in making division using divisors larger than the half of number tested, hence “number / 2” in the second version below. This caused 0 and 1 being added to ‘primes’ but I fixed it by moving number < 2 condition out of the loop. Now filtering of 0 and 1 happens before the loop is reached.

isPrime() with my modifications:

public boolean isPrime(int number) {
    if (number < 2) {
      return false;
    } 
    for (int i = 2; i <= number / 2; i++) {
      if (number % i == 0) {
        return false;
      }
    }
    return true;
  }

Result - 12.625 seconds

[Running] cd "/Users/jankes_mj/Documents/Coding/Codecademy Projects/Java/Prime Directive/" && javac PrimeDirective.java && java PrimeDirective
[989898989, 989898989, 989898989, 989898989, 989898989]

[Done] exited with code=0 in **12.625 seconds**

That’s almost 13 seconds faster and it’s only a short array with 9 elements. I imagine this would stand out even further if longer arrays had to be tested.

My full code:

import java.util.ArrayList;

class PrimeDirective {

  public boolean isPrime(int number) {
    if (number < 2) {
      return false;
    } 
    for (int i = 2; i <= number / 2; i++) {
      if (number % i == 0) {
        return false;
      }
    }
    return true;
  }

  public ArrayList<Integer> onlyPrimes(int[] numbers) {
    ArrayList<Integer> primes = new ArrayList<Integer>();
    for (int number : numbers) {
      if (isPrime(number)) {
        primes.add(number);
      }
    }
    return primes;
  }

  public static void main(String[] args) {

    PrimeDirective pd = new PrimeDirective();
    int[] numbers = { 989898989, 989898987, 989898989, 989898987, 989898989, 989898987, 989898989, 989898987, 989898989 };
    System.out.println(pd.onlyPrimes(numbers));
  }

}
2 Likes

There’s an even faster way to test for primality: trying to divide the number by divisors up to and including the square root of the number (e.g. divide up to and including 6 for 36, up to and including 8 for 65).

This is explained in more detail here.

1 Like

Thanks, victoria_dr! That’s a great tip.

sqrt(16) = 4
16 = 4 x 4;
16 = 2 x 8;

One of the divisors will always be <= 4. Seems so obvious when you know about it. :sweat_smile:

Here’s the same method with your suggestion implemented.

 public boolean isPrime(int number) {
    if (number < 2) {
      return false;
    }
    for (int i = 2; i <= Math.sqrt(number); i++) {
      if (number % i == 0) {
        return false;
      }
    }
    return true;
  }

I ran it a few times and it took just over a second. Best run: 0.97 sec. That’s a huge (!) improvement over the original 25 sec and the later 12.5 sec.

[Running] cd "/Users/jankes_mj/Documents/Coding/Codecademy Projects/Java/Prime Directive/" && javac PrimeDirective.java && java PrimeDirective
[989898989, 989898989, 989898989, 989898989, 989898989]

[Done] exited with code=0 in **0.97 seconds**
1 Like