Почему в методе findNextPrime нам нужно найти квадратный корень из 'num', sqt, и использовать его в цикле for?

Я пытаюсь решить проблему новичка «найти следующее простое число после заданного числа». Я видел этот код в Интернете, и он отлично работает, но я не могу понять, почему в методе findNextPrime нам нужно найти квадратный корень из 'num', sqt, и использовать его в цикле for. Может ли кто-нибудь объяснить мне математику и причины этого?

import java.util.Scanner;

public class NextPrime {

    public static void main(String[] args) {
        System.out.println("Enter the number to find the next prime to it.");
        Scanner sc = new Scanner(System.in);
        int i1 = sc.nextInt();
        sc.close();

        System.out.println("the next prime number to " + i1 + " is " + findNextPrime(i1));
    }

    public static int findNextPrime(int num) {
        while (true) {
            boolean isPrime = true;
            num += 1;
            int sqt = (int) Math.sqrt(num);
            for (int i = 2; i <= sqt; i++) {
                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                return num;
            }
        }

    }
}

person Thor    schedule 20.01.2016    source источник
comment
Если число n не делится ни на одно число, меньшее sqrt(n), то оно не может делиться ни на какое число большее, чем sqrt(n). если n == p * q, то либо p, либо q должны быть меньше sqrt(n)   -  person Miserable Variable    schedule 20.01.2016


Ответы (1)


ОК, найдите множители, например, 36. Вы получите 1,2,3,4,6,9,12,18,36.

Когда вы знаете, что 2 — это множитель, вы также можете понять, что 18 — это множитель. Для каждого множителя, меньшего, чем sqrt(36), он будет иметь соответствующий множитель, больший, чем sqrt(36). Таким образом, продолжая после половины пути, вы просто найдете факторы, которые вы уже нашли.

Итак, если вы знаете, что число не имеет делителей до середины, вы можете сделать вывод, что оно не имеет делителей.

person the pickle    schedule 20.01.2016