要检验一个数是不是质数,为什么我们要检验它是否只能被这个数的平方根整除?
当前回答
如果一个数n不是质数,它可以被分解成两个因子a和b:
n = a * b
现在a和b不可能都大于根号n,因为这样a * b就会大于根号n *根号n = n,所以在n的任何因式分解中,至少有一个因子必须小于根号n,如果我们找不到任何小于或等于根号的因子,n一定是质数。
其他回答
如果一个数n不是质数,它可以被分解成两个因子a和b:
n = a * b
现在a和b不可能都大于根号n,因为这样a * b就会大于根号n *根号n = n,所以在n的任何因式分解中,至少有一个因子必须小于根号n,如果我们找不到任何小于或等于根号的因子,n一定是质数。
因为如果一个因子大于根号n,那么与它相乘等于n的另一个因子必然小于根号n。
假设m =根号n,那么m × m = n。如果n不是质数,那么n可以写成n = a × b,所以m × m = a × b。注意,m是实数,而n、a和b是自然数。
现在有三种情况:
A > m⇒b < m ⇒A = m, b = m A < m⇒b > m
在这三种情况下,min(a, b)≤m。因此,如果我们搜索到m,我们一定会找到n的至少一个因子,这足以证明n不是质数。
为了测试一个数字n的质数,人们首先会期望一个循环,如下所示:
bool isPrime = true;
for(int i = 2; i < n; i++){
if(n%i == 0){
isPrime = false;
break;
}
}
上面的循环是这样做的:对于给定的1 < i < n,它检查n/i是否为整数(余数为0)。如果存在一个i,其中n/i是整数,那么我们可以确定n不是质数,此时循环终止。如果没有i, n/i是整数,那么n是素数。
和每一个算法一样,我们会问:我们能做得更好吗?
让我们看看上面的循环中发生了什么。
i的序列是:i = 2,3,4,…, n - 1
整数检查的顺序是:j = n/i,也就是n/2, n/3, n/4,…n (n - 1) /
如果对于某些i = a, n/a是一个整数,那么n/a = k(整数)
或者n = ak,显然是n > k > 1(如果k = 1,那么a = n,但我从来没有达到n;如果k = n,那么a = 1,但我从2开始
同样,n/k = a,如上所述,a是i的值,所以n > a > 1。
所以,a和k都是1和n之间的整数(排他)。由于i达到了该范围内的每一个整数,在某个迭代i = a时,在另一个迭代i = k时。如果n的质数检验对于min(a,k)失败,那么对于max(a,k)也会失败。所以我们只需要检查这两种情况中的一种,除非min(a,k) = max(a,k)(其中两次检查减少为一次),即a = k,此时a*a = n,这意味着a =根号(n)。
换句话说,如果n的质数检验对于某些i >=√(n)(即max(a,k))失败,那么对于某些i <= n(即min(a,k))也会失败。因此,如果我们运行i = 2到根号n的测试就足够了。
假设n不是一个质数(大于1),那么有数字a和b满足
n = ab (1 < a <= b < n)
通过将a<=b的关系乘以a和b,我们得到:
a^2 <= ab
ab <= b^2
因此:(注意n=ab)
a^2 <= n <= b^2
因此:(注意a和b是正的)
a <= sqrt(n) <= b
因此,如果一个数(大于1)不是质数,并且我们测试到该数的平方根的可除性,我们将找到其中一个因数。
推荐文章
- 如何计算圆周长上的一点?
- 从整数流中找到运行中位数
- 在日历应用程序中建模重复事件的最佳方法是什么?
- 在任何情况下,您更喜欢高大o时间复杂度算法而不是低大o时间复杂度算法吗?
- 如何使用JavaScript比较软件版本号?数量(只)
- 跳跃表vs.二叉搜索树
- 如何使四舍五入百分比加起来为100%
- 是否有可能得到一个函数的所有参数作为单一对象内的函数?
- LL和LR解析之间的区别是什么?
- log(n!) = Θ(n·log(n))?
- C语言中位反转的高效算法(从MSB->LSB到LSB->MSB)
- 递归还是迭代?
- 两个长度不等的表之间的排列
- 给出一个图像来表示和解决一个迷宫
- 如何在使用归并排序算法排序?