Finding Primes in Java

Question

I have a prime-finding class here that needs improvement.

Sample result:

Number of primes?
10
2 3 5 7 11 13 17 19 23 29
Total calculation time: 6 milliseconds
Calculation time per number: 0.6 milliseconds

As more prime numbers are calculated, the calculation time per number increases.

100 primes:

Number of primes? 
100 
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
...
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
Total calculation time: 23 milliseconds
Calculation time per number: 0.23 milliseconds

1000 primes:

Number of primes? 
1000 
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
...
7727 7741 7753 7757 7759 7789 7793 7817 7823 7829
7841 7853 7867 7873 7877 7879 7883 7901 7907 7919
Total calculation time: 269 milliseconds
Calculation time per number: 0.269 milliseconds

Main class

import java.util.NoSuchElementException;
import java.util.Scanner;
public class Main {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 System.out.println("Number of primes?");
 boolean validInput = false;
 int i = 0;
 while (!validInput) {
 try {
 i = sc.nextInt();
 validInput = true;
 } catch (NoSuchElementException e) {
 // validInput stays false
 System.out.println("That's not an integer. Try again:");
 sc.next();
 }
 }
 boolean warning = false;
 if (i > 50000) {
 System.out
 .println("The program will not allow this many primes to be calculated!");
 sc.close();
 return;
 } else if (i > 20000) {
 System.out.println("WARNING! Large amount of memory is needed!");
 warning = true;
 }
 if (i > 6400) {
 System.out
 .println("WARNING! It will take more that 2 millisecond per number for calculation!");
 warning = true;
 } else if (i > 3450) {
 System.out
 .println("WARNING! It will take more that 1 millisecond per number for calculation!");
 warning = true;
 }
 if (i > 6650) {
 System.out
 .println("WARNING! It will take more that 15 seconds for calculation!");
 warning = true;
 }
 if (warning) {
 System.out.println("Are you sure you want to continue? (Y/N)");
 while (true) {
 String yn = sc.nextLine();
 if (yn.equalsIgnoreCase("Y")) {
 break;
 } else if (yn.equalsIgnoreCase("N")) {
 sc.close();
 System.out.println("Bye!");
 return;
 }
 }
 }
 long l = System.currentTimeMillis();
 Prime p = new Prime(i);
 printSortedLongArray(p.getPrimes(i));
 long timeNow = System.currentTimeMillis();
 System.out.println("Total calculation time: " + (timeNow - l)
 + " milliseconds");
 System.out.println("Calculation time per number: "
 + ((timeNow - l) / (double) i) + " milliseconds");
 System.out.println("Bye!");
 sc.close();
 }
 public static void printSortedLongArray(long[] a) {
 long nums = 0;
 int len = Long.toString(a[a.length - 1]).length();
 for (long l : a) {
 System.out.print(l);
 nums++;
 if (nums % 10 == 0) {
 System.out.println();
 continue;
 }
 for (int i = Long.toString(l).length(); i <= len; i++) {
 System.out.print(" ");
 }
 }
 if (nums % 10 != 0) {
 System.out.println();
 }
 }
}

Prime class

import java.util.LinkedList;
import java.util.List;
public class Prime {
 long[] primes;
 public Prime(int max) {
 primes = new long[max];
 int j = 0;
 for(long i = 1; j < max; i++) {
 if(isPrime(i)) {
 primes[j] = i;
 j++;
 }
 }
 }
 public long[] getPrimes(int max) {
 return primes;
 }
 public static boolean isPrime(long l) {
 return l != 1 && getFactors(l).length == 2;
 }
 public static long[] getFactors(long l) {
 List<Long> list = new LinkedList<Long>();
 for(long i = 1 ; i <= l / 2 ; i++) {
 if(l % i == 0) {
 list.add(i);
 }
 }
 list.add(l);
 long[] result = new long[list.size()];
 int len = list.size();
 for(int i = 0; i < len; i++) {
 result[i] = list.get(i);
 }
 return result;
 }
}

My questions:

1. Is there a better way of doing this? If so, how?
2. Is the separate Prime class necessary?

Any criticism is welcome!

• RubberDuck: This post was mentioned on meta.

Answer 1

Is there a better way of doing this? If so, how?

Yes, there is. Your current algorithm is \$O \left( n + \left( n \times \dfrac{n}{2} \right) + \left( \dfrac{n}{2} \right) \right) \,ドル or \$ O(n^{2}) \$. (The first \$n\$ is the iterating of the numbers, the \$ \left( n \times \dfrac{n}{2} \right) + \left( \dfrac{n}{2} \right) \$ is the time complexity of a triangular number.)

If you use the Sieve of Eratosthenes, which works like this...

enter image description here
_{(image courtesy of linked Wikipedia article)}

you get \$ O \left(n \left( \log n \right) \left( \log \log n \right) \right) \,ドル which is faster. See this Stack Overflow question on how the time complexity was determined.

• 200_success: The sieve-of-eratosthenes is a much better strategy, especially when you want to find many primes.
• TheCoffeeCup: But how am I supposed to determine the number of primes that a number will produce? e.g. Input was 10, so what number do I set as max?
• mleyfman: There is no deterministic formula for the number of primes below n. Furthermore, the "density" of primes decreases with n (but is always positive), and so it will always take longer and longer to find more primes.
• 200_success: @mleyfman A reasonable estimate of the size of the sieve needed is 1.4 max ln(max), where the factor of 1.4 inflates the estimate generously.
• 200_success: Alternatively, implement a Prime class that presents the illusion of an "infinite" sieve. It's tricky to do implement correctly, though.

Answer 2

For finding all primes, a sieve is better. However for a general isPrime function, there is a much better way to do it.

Your algorithm finds all factors and returns true if there are exactly 2. In reality, you can stop when you hit the first one. Plus, you don't have to check if 1 is a factor, you only have to check if primes are factors, and you only have to check primes up to the square root of the number. As an added bonus, you already have a list of primes to use in your checks.

Answer 3

Your algorithm is a little slow because it is O(n^2), you can improve on this somewhat.

The prime number sieve is mentioned in another answer, but it's a little harder to use if you want to find a number of primes, rather than all the primes up to a number

With Java 8 you can use an infinite IntStream like so:

Collection<Integer> primes(int numPrimes) {
 final List<Integer> primes = new ArrayList<>(numPrimes);
 IntStream.iterate(2, i -> i + 1).
 filter(i -> {
 for (int prime : primes)
 if (i % prime == 0)
 return false;
 return true;
 }).limit(numPrimes).
 forEach(primes::add);
 return primes;
}

First create a List of the appropriate size to hold the output.

Now create an infinite stream using IntStream.iterate(2, i -> i + 1). All you need to do, is filter the stream so that each number generated is not divisible by each of the primes already generated:

filter(i -> {
 for (int prime : primes)
 if (i % prime == 0)
 return false;
 return true;
})

So you loop over the primes already generated and check whether the current number is divisible by each.

Now limit the stream to the number you want to generate with limit(numPrimes).

Finally dump the result into the primes list forEach(primes::add).

You have to ensure that the stream runs sequentially, so don't call parallel.

A few further comments, use printf rather than string concatenation is output:

System.out.printf("Total calculation time: %s ms%n", (timeNow - l));

You are getting a little carried away with closing your Scanner, to the extent that it pollutes your code. Use a try-with-resources:

try(Scanner sc = new Scanner(System.in)) {
}

You code looks more like a script than a well structured program - everything is in main.

Your large block of code spitting out warnings is certainly doesn't belong in the main method - you should create another method to deal with this. Possibly even a separate class - or for full flexibility a set of classes implementing an interface. So that you can add new warnings whilst sticking by the Open-Closed-Principal.

Similarly, this block of code should be in method returning a boolean:

System.out.println("Are you sure you want to continue? (Y/N)");
while (true) {
 String yn = sc.nextLine();
 if (yn.equalsIgnoreCase("Y")) {
 break;
 } else if (yn.equalsIgnoreCase("N")) {
 sc.close();
 System.out.println("Bye!");
 return;
 }
}

You might also want to consider using a Console rather than a Scanner as you can prompt for input rather than have to println then read.

P.S. pre Java 8 primes would look like this:

Collection<Integer> primes(int numPrimes) {
 final List<Integer> primes = new ArrayList<>(numPrimes);
 int num = 2;
 while (primes.size() < numPrimes) {
 if (isPrime(num, primes))
 primes.add(num);
 num++;
 }
 return primes;
}
boolean isPrime(final int num, final List<Integer> primes) {
 for (int prime : primes)
 if (num % prime == 0)
 return false;
 return true;
}

• fgb: Your algorithm appears to be the unfaithful sieve (see cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf). It would be much more efficient to check factors up to the square root of each number instead.
• Boris the Spider: @fgb I suppose one could do that - although being as it only checks prime factors and the density of primes decreases exponentially along the number line, I'm not sure it would be that much more efficient.

Answer 4

The sieve is optimal for what you try to do. In your code, the isPrime method is not efficient. An easy optimisation is to start your loop from 2 (1 is redundant) and finish your loop on \$\sqrt{n}\$ (this is well known in number theory). Also there is no need to use a list, simply return false when you detect a non prime in the loop. So the whole thing can take a few lines:

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

• Stephan Branczyk: "An easy optimisation is to start your loop from 2 (1 is redundant)". Actually, you mean an easy micro-optimization (not worth making at all) is to start from 2. That micro optimization doesn't save you much time at all. I think you meant to say that all the even numbers are redundant since we already know they're all divisible by two. That means you can just increment your loop by two instead of just one and only work on the odd numbers, thus saving you half the time. Now, that's an optimization worth making. Of course, in that case you'd need to start your loop with an odd number as well.