判断一个数是否为质数(素数)的4种方法 | 您所在的位置:网站首页 › 100以为的质数有什么 › 判断一个数是否为质数(素数)的4种方法 |
目录 1.什么是质数? 2.如何判断是否为质数? 方法1 方法2 方法3 方法4 1.什么是质数?首先来看质数的概念: 质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数。(也可定义为只有1与该数本身两个正因数的数) 图1 数字12不是质数,而数字11是质数 如上图所示,数字12可以将每4个分成一组,一共3组;而数字11将每4个、每5个、每3个分成一组都无法全部分完,而有剩余,因此将数字11称为质数。 2.如何判断是否为质数? 质数的特点如下: 一个自然数(如1、2、3、4、5、6等)若恰有两个正约数(1及此数本身),则称之为质数。 方法1根据质数的约数只有1和本身这一特点,可以首先想到最直观的方法。第一种方法就是判断一个数是否能被比它小的数整除。 方法1的时间复杂度是O(n)。 public static boolean isPrime(int n){ //n3时,质数无法被比它小的数整除 for(int i = 2; i < n; i++){ if (n % i == 0) { return false; } } return true; } 方法2当一个数不是质数时,必定存在两个约数,一个大于等于sqrt(n),另一个小于sqrt(n)。利用这种特性,可以对方法1进行改进,只判断数n能否被小于sqrt(n)的数整除。 方法2的时间复杂度是O(sqrt(n))。 图2 筛选判断集,只选择小于等于sqrt(n)的集合public static boolean isPrime(int n) { if (n 1; } //判断一个数能否被小于sqrt(n)的数整除 int sqrt = (int)Math.sqrt(n); for (int i = 2; i |
CopyRight 2018-2019 实验室设备网 版权所有 |