I got carried away recently with simple numbers and I needed a program to check the number for simplicity.

I check a huge number of numbers and work outside of long. First time working with BigInteger. Therefore, I would be happy to hear opinions about the effectiveness of the code. Is it possible to increase productivity somewhere?

The algorithm is simple:

  • check whether 0,1,2 is equal to or less than zero.
  • check whether it is divisible by at least one odd starting from 3 to the square root of the number itself.

Code:

public static boolean isPrime(BigInteger number) { if (number.compareTo(new BigInteger("0")) < 0) throw new IllegalArgumentException("The number should be positive"); if (number.toString().equals("1") || number.toString().equals("0")) return false; // if the number is even return FALSE, unless the number is "2". if (isEven(number)) { if (number.toString().equals("2")) { return true; } return false; } long limit = sqrt(number).longValue(); // A loop for searching a divider. If no divider found - return "true". for (long i = 3; limit >= i; i += 2) { // if (number % i == 0) if (number.mod(new BigInteger(String.valueOf(i))).toString().equals("0")) { // System.out.println("The first divider is " + i); return false; } } return true; } public static boolean isEven(BigInteger number) { if ((number.and(new BigInteger("1"))).toString().equals("0")) return true; else return false; } public static BigInteger sqrt(BigInteger N) { final BigInteger TWO = new BigInteger("2"); BigInteger result = N.divide(TWO); while (result.multiply(result).subtract(N).compareTo(BigInteger.ONE.divide(new BigInteger("100000000"))) > 0) result = result.add(N.divide(result)).divide(TWO); return result; }
  • one
    Why write your method? You can use isProbablePrime() , and then check with any test of simplicity that it is really a simple number. - Arsenicum
  • So it is this test of simplicity that I am trying to write here. :) - Metaphysics

1 answer 1

  1. You don’t need to compare the string representations of BigInteger , so you can jump on the fact that "2".compareTo("10") == 1 , and constant conversions to BigInteger -> String will decrease performance. Compare yourself BigInteger 's: BigInteger.ONE.equals(number) or BigInteger.valueOf(2).equals(number) or new BigInteger("2").equals(number) . BigInteger.valueOf(2) preferable, since this method will cache the result and will not recreate the BigInteger object each time (relevant for numbers in the range [-16, 16] ).
  2. Highlight new BigInteger("100000000") into a constant, so you will avoid the permanent re-creation of this object. In general, you have some kind of porridge with constant BigInteger : you use the constant BigInteger.ONE , then you create a new object new BigInteger("1") . Bring everything to constants.
  3. Get into the habit of comparing objects through equals first to write the object that is guaranteed not to be null , in your case - constants with which you compare numbers.
  4. You check BigInteger simplicity, and you have a long limit as the upper limit for checking the dividers. On large numbers (from 3 037 000 500 and more) your code will stop working due to overrun long . Do a loop with a BigInteger counter.
  5. Your isEven method can be written shorter and more optimal: return number.getLowestSetBit() != 0; .

  6. In general, the design of the form

     if (/* условие */) { return true; } else { return false; }

    - not the best practice. If, in addition to return there is nothing in the code blocks and is not foreseen, it is better to replace such constructions with the return /* условие */; . If the condition is too complicated, it is broken down into several sub-conditions, assigning their values ​​to variables with talking names.

  7. Optimization: to reduce the number of calculations, you can use the isProbablePrime method (as suggested by @Arsenicum) or independently implement a Miller-Rabin probabilistic check (if you are seeking to delve deeper into the mathematical part of the problem).
  8. Another optimization: you can implement the sieve of Eratosthenes - so you avoid unnecessary checks for divisibility, but significantly increase memory consumption.