 # 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)) {
}
}
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. 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