Определение того, является ли число 4 простым или нет?

Question

Вот моя программа, внутри for loop Math.sqrt(n) - Я думаю, что здесь есть ошибка.

import java.util.Scanner; 

public class PrimeNoCheck { 

    public static void main(String[] args) { 
     Scanner s = new Scanner(System.in); 

     System.out.print("Enter a number : "); 

     int n = s.nextInt(); 

     if (isPrime(n)) { 
      System.out.println(n + " is a prime number"); 
     } else { 
      System.out.println(n + " is not a prime number"); 
     } 

    } 

    public static boolean isPrime(int n) { 
     if (n <= 1) { 
      return false; 
     } 

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

     return true; 
    } 
} 

Answer 1

алгоритм: Чтобы проверить, если п простое число, вы должны попытаться разделить его на все числа от 2 (1 бесполезен), в SQRT (п), включены.

Вам не нужно проверять после sqrt (n), потому что, если n можно разделить на X, больше, чем sqrt (n), его также можно разделить на Y (n/X), меньшее, чем sqrt (n) или Z, меньше Y, если Y не является простым.

Ошибка в вашем коде заключается в том, что вы останавливаете перед sqrt (n).

С вашим кодом 4, 9, 25, ... видны как простые и все простые^2 также.

просто заменить, что: < = вместо <

for (int i = 2; i <= Math.sqrt(n); i++) {