Пояснение к методу isPrime () - PullRequest
Новая
       35

Пояснение к методу isPrime ()

0 голосов
/ 10 июля 2020

Может ли кто-нибудь помочь мне прояснить, что происходит, когда через этот метод передается целое число, поскольку я изо всех сил пытаюсь понять. Спасибо! 

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

1 Ответ

0 голосов
/ 10 июля 2020

Когда вы передаете число в функцию, сначала нужно быстро проверить случай, когда 1 не является простым и может делить все остальные положительные целые числа без остатка. Итак, это специально проверенный случай: 

if (n == 1) {
    return false;
}

Затем, для l oop вы проверяете, делится ли данное число на любое целое число до половины заданного числа, что позволяет нам решить, является ли оно простое или нет. Если он делится, значит, он не простой, верните false. Способ проверить, делится ли число или нет, - использовать оператор mod .

Но есть проблема; как сказал @ W JS в разделе комментариев, вам не нужно проверять все числа до n / 2, из Wikipedia :

Чтобы проверить простоту 100 путем пробного деления, рассмотрим все целые делители 100:

2, 4, 5, 10, 20, 25, 50 Самый большой множитель равен 100/2 = 50. Это верно для всех n: all делители меньше или равны n / 2. Осмотрев делители, выясняется, что некоторые из них лишние. Список делителей может быть записан как:

100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2, что демонстрирует избыточность. После проверки делителя 10, который равен √100, первый делитель будет просто делимым предыдущего делителя. Следовательно, можно исключить тестовые делители больше √n.

Таким образом, ваш код может быть более эффективным следующим образом: 

for (int i = 2; i < Math.sqrt(n)+1; i++) {
    if (n % i == 0) {
        return false;
    }
}

Наконец, если вы не можете разделить свои число с любым числом до его квадрата root, тогда это означает, что оно простое, поэтому верните true.

...