Determine whether number is prime [closed]

Question

The code determines if a number is prime or not, and there are some initial checks to rule out some values.

I would like feedback on how to speed up this program. I am really new to threads - might that be useful? I really don't know where to begin multithreading this code.

import java.io.*;
import java.math.BigInteger;

/*
A known proof exists for prime numbers not withstanding the values 2 and 3, such that
all prime numbers are of the form (6k)+-1.

For example:
{(5 = 6(1)-1),(13 = 6(2)+1),(1 = 6(0)+1),(5081 = 6(847)-1)...(anyPrimeNumberNot2or3 = (6k)+-1)}
*/

class primeFinder {

  // takes your number to check
  static boolean isPrime(BigInteger n) {
    BigInteger two = new BigInteger("2");
    BigInteger three = new BigInteger("3");
    BigInteger five = new BigInteger("5");
    BigInteger six = new BigInteger("6");

    // we omit one because isnt prime because it has less
    // than 2 divisors, and we also omit negatives
    if (n.compareTo(BigInteger.ONE) != 1) return false;

    // 2 and 3 are both prime so we return true for each
    if (n.compareTo(three) != 1) return true;
    /*
    check here to see if divisible by two or three to speed things up
    */

    try {
      if (n.mod(two) == BigInteger.ZERO || n.mod(three) == BigInteger.ZERO) return false;
    } catch (ArithmeticException a) {
      return false;
    }

    /*
    starting at 5, check for divisibility based on our proof.
    incrementing i by 6 each time gives us a chance to check when
    the index is a value of 6k.

    it begins by squaring 5 to compare with 25. If n is less than 25
    and it is divisible by 2 or three, it will have been caught by this
    point in the last check. We use this squaring iteratively because it
    concludes primality at a much faster rate by checking realatively large
    ranges of numbers instead of one integer at a time.

    e.g. n = 18 or 15

      N will have been thrown already because numbers
      that small can only be divisible by a few integers that are all divisible
      by two or three. ,

      however, if n =  19, than it will be found to be prime and the program
      will return true after failing the second argument of the for loop...

      e.g. (25 !<= 19)
    */

    for (BigInteger i = five; i.pow(2).compareTo(n) != 1; i = i.add(six))

      /*
      otherwise, if the number is larger than 25 (needs to be for this assignment),
      we check to see if we can mod it by i or if we can mod it by i + 2. The first
      reflects checking the first number not divisible by 2 or 3 in the counting
      sequence. The second check is to see if we add 2 to i, will n divide evenly
      into it.

      for example, in the first iteration we have i = 5. we know that n is not divisible
      by 2 or 3, so we see if it is divisible by five (four is divisible by 2!). We also
      check if n is divisible by i + 2 = 7 (i +1 = 6 % 3 = 0, it would have been caught).

      Assuming that our proof holds, the following iterations will abide by this structure.

      e.g.=> n=223 (known prime), i = i+6 = 11 (second iteration)

        223 % 11 = 3
        i can be prime; at this point we have determined that i is not divisible by 2 || 3,
        so integers {6,8,9,10} have been checked. As for 7, it was checked in the second half
        of the first iteration; recall (n % i + 2) => (223 % 5 + 2) => (223 % 7).

      or

        223 % 13 = 2. At this point we have checked n % {5,6,7,8,9,10,11,12,13}.

        this will continue until i squared >= n, however this will probably be overkill,
        since we really only need to check up until sqrt(n). This method was difficult enough
        to implement and i dont think it would work well with such a limit; It also retains a
        more robust proofing method in the code.
      */

      if (n.mod(i) == BigInteger.ZERO || n.mod(i.add(two)) == BigInteger.ZERO) return false;

    return true;
  }
  // Main

  public static void main(String args[]) {

    long start = System.nanoTime();
    // sigh of simplicity
    if (args.length != 1) {

      System.out.println(
          "usage: java primeFinder <insert integer here (up quintillions"
              + "- 19 digits) - false primes will return faster>");
      return;
    } else {

      long l = Long.parseLong(args[0]);
      BigInteger n = BigInteger.valueOf(l);

      if (isPrime(n)) System.out.println("true");
      else System.out.println("false");
    }

    long end = System.nanoTime();
    System.out.println(((end - start) / 1000000) + " ms");
  }
}
```

Answer 1

I am really new to threads and I can't see where it would be most useful, but it is required.

Why is multithreading required? You may not get the performance boost you're looking for just by implementing multiple threads. Or do you just mean that you require better performance than you're getting? (Why?) I'll address both.

BigInteger

Your main function limits the input to the range of long but your implementation then uses BigInteger anyway. Either preserve the input BigInteger made from the string input, or otherwise you should be able to work only with long.

When I tried changing isPrime to take a long, it was much, much slower actually...! But then after I swapped i^2 <= n for i <= Math.sqrt(n) to prevent i^2 from overflowing the size of a long, then it was about 8 times faster than the BigInteger version.

Single thread performance

The only part of the program that takes any time at all is the for loop. Since i is always increasing, there's no opportunity to cache prior calculations within the loop.

The intermediate values aren't useful to other calculations on different inputs because the entire loop has to be run for a different n.

If it is likely that the function will be called with the same input repeatedly, you might benefit from caching the output of the function in a lookup table such as a HashMap.

Multithreaded performance

Multithreading on a single core will only increase performance if the core is not fully utilized. For instance, it might be waiting on network, and multithreading means it can swap to a new job while waiting. But this program is fully utilizing a single core as there is no need to wait for anything.

Adding threads will allow you to take advantage of multiple cores, which doesn't happen with a single thread, but you'll need to be very careful with your implementation.

If we knew how many times the for loop has to run, we could just divide up the work between as many threads as we have cores, and start each thread with a different starting value and upper bound of i.

But we can't know that, and in fact most of the time the function will return early, so how about a system where a thread reserves a fixed amount of work, comes back with an answer, then requests more work until all the work is done or a false was found. The problem is that starting up a Thread can take a long time, so you'd want to make sure that each thread is started with enough work to keep it busy for a while. You'd also want to keep the threads alive between batches instead of destroying them, so using something like Executors.newFixedThreadPool.

So then ask are you going to set up a thread pool every single time you call the function? If you're going to call it more than a few times, you might want to start the thread pool and be ready for calls to the function.

Formatting

Class names should begin with a capital letter.

Sometimes comments do belong just to specific lines, but huge blocks of comments can make it harder to see what's going on. Sometimes it's best just to explain how the algorithm works in one go, and then let the code speak for itself.

class PrimeFinder {

    /*
     * A known proof exists for prime numbers not withstanding the values 2 and 3,
     * such that all prime numbers are of the form (6k)+-1.
     * 
     * For example: {(5 = 6(1)-1),(13 = 6(2)+1),(1 = 6(0)+1),(5081 =
     * 6(847)-1)...(anyPrimeNumberNot2or3 = (6k)+-1)}
     * 
     * 
     * we omit one because isnt prime because it has less than 2 divisors, and we
     * also omit negatives
     * 
     * 2 and 3 are both prime so we return true for each
     * 
     * starting at 5, check for divisibility based on our proof. incrementing i by 6
     * each time gives us a chance to check when the index is a value of 6k.
     * 
     * it begins by squaring 5 to compare with 25. If n is less than 25 and it is
     * divisible by 2 or three, it will have been caught by this point in the last
     * check. We use this squaring iteratively because it concludes primality at a
     * much faster rate by checking realatively large ranges of numbers instead of
     * one integer at a time.
     * 
     * e.g. n = 18 or 15
     * 
     * N will have been thrown already because numbers that small can only be
     * divisible by a few integers that are all divisible by two or three. ,
     * 
     * however, if n = 19, than it will be found to be prime and the program will
     * return true after failing the second argument of the for loop...
     * 
     * e.g. (25 !<= 19)
     * 
     * otherwise, if the number is larger than 25 (needs to be for this assignment),
     * we check to see if we can mod it by i or if we can mod it by i + 2. The first
     * reflects checking the first number not divisible by 2 or 3 in the counting
     * sequence. The second check is to see if we add 2 to i, will n divide evenly
     * into it.
     * 
     * for example, in the first iteration we have i = 5. we know that n is not
     * divisible by 2 or 3, so we see if it is divisible by five (four is divisible
     * by 2!). We also check if n is divisible by i + 2 = 7 (i +1 = 6 % 3 = 0, it
     * would have been caught).
     * 
     * Assuming that our proof holds, the following iterations will abide by this
     * structure.
     * 
     * e.g.=> n=223 (known prime), i = i+6 = 11 (second iteration)
     * 
     * 223 % 11 = 3 i can be prime; at this point we have determined that i is not
     * divisible by 2 || 3, so integers {6,8,9,10} have been checked. As for 7, it
     * was checked in the second half of the first iteration; recall (n % i + 2) =>
     * (223 % 5 + 2) => (223 % 7).
     *
     * or
     * 
     * 223 % 13 = 2. At this point we have checked n % {5,6,7,8,9,10,11,12,13}. this
     * will continue until i squared >= n, however this will probably be overkill,
     * since we really only need to check up until sqrt(n). This method was
     * difficult enough to implement and i dont think it would work well with such a
     * limit; It also retains a more robust proofing method in the code.
     */
    static boolean isPrime(final long n) {
        if (n <= 1) {
            return false;
        }
        if (n <= 3) {
            return true;
        }
        if (n % 2 == 0 || n % 3 == 0) {
            return false;
        }
        for (long i = 5; i <= Math.sqrt(n); i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String args[]) {
        if (args.length != 1) {
            System.out.println("usage: java primeFinder"
                    + "<insert integer here (up quintillions - 19 digits)"
                    + " - false primes will return faster>");
            return;
        }
        long start = System.nanoTime();
        System.out.println(isPrime(Long.valueOf(args[0])));
        long end = System.nanoTime();
        System.out.printf("%d ms", ((end - start) / 1000000));
    }
}
```