Prime（素数）判定（java）

By Diskobólos at: 2020-02-15

Prime（素数）判定（java）

2020-02-15

素数定义：

大于1，且只有1和它本身两个因数，即不能写成 n=p*q（p、q均不为1）

判定算法：

方法一：根据定义从2到n-1，依次判断n是否能整除，如果都不能则为素数

1
2
3
4
5
6
7
8
private boolean isPrime(int m){
       for(int i=2;i<m;i++){
           if(m%i==0){
               return false;
           }
       }
       return true;
   }

方法二：方法一的改进，n=p*q, p,q里面必然有个数小于等于sqrt（n），因此只需要判断1<x<=sqrt(n)部分

1
2
3
4
5
6
7
8
9
10
11
private boolean isPrime(int m){
       if(m%2==0){
           return false;
       }
       for(int i=2;i<Math.sqrt(m);i++){
           if(m%i==0){
               return false;
           }
       }
       return true;
   }