Prime Directive project - solution

Projects
1

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));
  }

}
5 Likes
2

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.

2 Likes
3

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**
2 Likes
5

prime number
prime number880×1223 65.8 KB

can anyone help with my code it keeps returning true when i input a number that isn’t prime. TIA

6

I had this issue too until I noticed I wasn’t saving before running in bash.

For example, in your:
System.out.println(pd.isPrime(6));
If you were to put “7”, hit save, and run the program in bash, you would get “true” returned. If you then changed the number in your middle window where you code to “28”, but you don’t hit the save button, and you run it in bash again, you will still get “true”, not “false” as it should be. This is because the code running is the last one you saved, not what is currently being shown. In other words, you must save before every test for the test to be accurate. If that fails, then you may want to refresh your window, as that can sometimes help when code isn’t running right.

Hope this helps!