Я пытаюсь решить проблему новичка «найти следующее простое число после заданного числа». Я видел этот код в Интернете, и он отлично работает, но я не могу понять, почему в методе 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;
}
}
}
}
n
не делится ни на одно число, меньшееsqrt(n)
, то оно не может делиться ни на какое число большее, чемsqrt(n)
. еслиn == p * q
, то либоp
, либоq
должны быть меньшеsqrt(n)
- person Miserable Variable   schedule 20.01.2016