素数判定

概念

描述

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数

思路

循环判断至被求数的二次方根，降低时间复杂度

Code

public class Prime {
    static boolean isPrime(int x) {
        int i;
        for(i=2;i<=Math.sqrt(x);i++) { if(x%i==0) break; } if(i>Math.sqrt(x)&&x!=1)
            return true;
        else
            return false;
    }
    public static void main(String[] args) {
       Scanner as=new Scanner(System.in);
       int n;
       while(as.hasNext()) {
           n=as.nextInt();
           if(isPrime(n)) {
               System.out.println(n+" is Prime!");
           }else {
               System.out.println(n+" is not Prime!");
           }
       }

    }

}