算法:如何判断一个数是否是质数

落日映苍穹つ 2022-03-21 14:39 506阅读 0赞

# 质数的定义 #

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。  
大于1的自然数若不是素数，则称之为合数（也称为合成数）。  
例如，5是个素数，因为其正约数只有1与5。而6则是个合数，因为除了1与6外，2与3也是其正约数。  
算术基本定理确立了素数于数论里的核心地位：任何大于1的整数均可被表示成一串唯一素数之乘积。为了确保该定理的唯一性，1被定义为不是素数，因为在因式分解中可以有任意多个1（如3、1×3、1×1×3等都是3的有效约数分解）。

# 欧几里得定理 #

古希腊数学家欧几里得于公元前300年前后证明有无限多个素数存在（欧几里得定理）。现时人们已发现多种验证素数的方法。其中试除法比较简单，但需时较长：设被测试的自然数为 n，使用此方法者需逐一测试2与 根号n之间的整数，确保它们无一能整除n

以上摘抄维基百科

# java代码如下 #

public class sushu {
        public static boolean isPrime(int n){
            if(n<2){
                return false;
            }
            for(int i=2;i*i<=n;i++){
                if(n%i==0){
                    return false;
                }
            }
            return true;
        }
    
        public static void main(String[] args) {
            boolean prime = isPrime(12);
            System.out.println(prime);
        }
    }

# 说明: #

正常是从1-n全部遍历.为什么只要遍历到根号n就行了呢??  
因为如果是素数的话,存在约束p1,p2(都大于1的),其中p1<=根号n,p2>=根号n  
也就是说素数n,一定会有1个小于根号n的约数p  
举例:素数77=7\*11,那么必定有一个约数7,满足7<根号77  
反之如果n没有1个小于根号n的约数p的话,那么就不是素数,就只能是质数了  
举例:质数23,在1,2,3,4都不是23的约数的情况下,就不可能是素数了.就没有必要在去考验5-22了