判断一个数是否为素数(质数)
程序员文章站
2022-03-18 16:57:23
质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。 ......
定义
质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
实现
直观的方法
int isprime(int x) { if (x < 2) return false; // 小于2的数都不是质数 for (int i = 2; i < x; i++) if (x % i == 0) return false; return true; }
显然这个算法的复杂度为\(o(n)\)。
更快的方法
我们知道,一个数如果可以进行因数分解,那么分解时得到的两个数一定是一个小于等于\(sqrt(n)\),一个大于等于\(sqrt(n)\)。所以,循环没有必要从\(2\)到\(x-1\),只需要从\(2\)到\(sqrt(n)\)就好了,那么这个算法的时间复杂度就为\(o\left(sqrt(n)\right)\)。
int isprime(int x) { if (x < 2) return false; // 小于2的数都不是质数 for (int i = 2; i <= int(sqrt(x)); i++) // 从2到sqrt(x) if (x % i == 0) return false; return true; }
当然,这个算法还可以继续优化,我们可以判断2是不是这个数的约数,然后就可以从\(3\)开始循环到\(sqrt(n)\)了,每次循环\(i+2\),那么这个算法的复杂度就为\(o(sqrt(n)/2)\)。
int isprime(int x) { if (x < 2) return false; // 小于2的数都不是质数 if (x != 2 && x % 2 == 0) return false; // 不是2且能被2整除的数都不是质数 for (int i = 3; i <= int(sqrt(x)); i += 2) // 每次循环加2 if (x % i == 0) return false; return true; }
还有更快的吗?——埃拉托斯特尼筛法
即使是上述的算法,在遇到很大的数字\((n\ge{100,000,000})\)的时候,还是很慢。
那还有没有更快的算法呢?答案是有的,埃拉托斯特尼筛法就是其中之一。
我们可以把从\(2\)到\(maxn\)的数储存为一张表,例如bool prime[maxn];
。
然后我们遍历这个数组,把\(i\)的倍数从数组中去掉,这样我们就得到了一张从\(2\)到\(maxn\)的质数的表。
需要判断一个数是否为质数的时候只需要查询这张表就可以了,例如if (prime[i]) // 你的操作
。
void getprime(int maxn) { for (int i = 0; i <= maxn; i++) prime[i] = 1; // 全部定义为质数 prime[0] = prime[1] = 0; for (int i = 2; i <= maxn; i++) { if (!prime[i]) continue; for (int j = i * 2; j <= maxn; j += i) prime[j] = 0; // i的倍数标记为合数 } }
引用
素数的四种判断方法、实现及比较: