2

Увлёкся недавно простыми числами и мне понадобилась программка для проверки числа на простоту.

Проверяю огромное количество чисел и работаю за пределами long. Первый раз работаю с BigInteger. Поэтому был бы рад услышать мнения по поводу эффективности кода. Можно ли здесь где-нибудь увеличить производительность?

Алгоритм прост:

  • проверка равно ли 0,1,2 или меньше ли нуля.
  • проверка делится ли без остатка на хотя бы одно нечётное начиная от 3 до квадратного корня самого числа.

Код:

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;
}
2
  • 1
    А зачем писать свой метод? Можно использовать isProbablePrime(), а потом проверять каким-нибудь тестом простоты, что это действительно простое число.
    – Arsenicum
    Commented 9 мар. 2016 в 5:36
  • Так именно этот тест простоты я здесь и пытаюсь написать.:) Commented 9 мар. 2016 в 7:58

1 ответ 1

7
  1. Не нужно сравнивать строковые представления BigInteger, так вы можете напороиться на то, что "2".compareTo("10") == 1, да и постоянные конвертации BigInteger -> String будут снижать производительность. Сравнивайте сами BigInteger'ы: BigInteger.ONE.equals(number) или BigInteger.valueOf(2).equals(number) или new BigInteger("2").equals(number). BigInteger.valueOf(2) предпочтительнее, так как этот метод закеширует результат и не будет каждый раз пересоздавать объект BigInteger (актуально для чисел в диапазоне [-16, 16]).
  2. Выделите new BigInteger("100000000") в константу, так вы избежите постоянного пересоздания этого объекта. Вообще, у вас какая-то каша с константными BigInteger'ами: то вы используете константу BigInteger.ONE, то создаёте новый объект new BigInteger("1"). Приведите всё к константам.
  3. Заведите привычку, сравнивая объекты через equals первым писать тот объект, который гарантированно не null, в вашем случае - константы, с которыми вы сравниваете числа.
  4. Вы проверяете на простоту BigInteger'ы, а в качестве верхней границы для проверуи делителей у вас long. На больших числах (от 3 037 000 500 и больше) ваш код перестанет работать из-за переполнения long'а. Делайте цикл со счётчиком BigInteger.
  5. Ваш метод isEven можно записать короче и оптимальнее: return number.getLowestSetBit() != 0;.
  6. Вообще, конструкции вида

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

    – не самая лучшая практика. Если кроме return в блоках кода ничего нет и не предвидится, лучше заменять такие конструкции на return /* условие */;. Если условие слишком сложное, его разбивают на несколько подусловий, присваивая их значения переменным с говорящими именами.

  7. Оптимизация: для сокращения числа расчётов можно использовать метод isProbablePrime (как предложил @Arsenicum) или самостоятельно реализовать вероятностную проверку Миллера-Рабина (если вы стремитесь поглубже вникнуть в математическую часть задачи).
  8. Ещё оптимизация: можно реализовать решето Эратосфена - так вы избежите ненужных проверок на делимость, но существенно увеличите потребление памяти.

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.