赞
踩
素数,也就是我们常说的质数,官方解释为在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数.
由定义知,对于一个自然数n, 如果从 2 - n -1之间的任意数 i,n均不能被 i 整除,则 n 为素数. 于是通过一个很简单的for循环,我们便很容易的写出来最简单的素数判断函数!
bool isPrime(int num){
for(int i = 2;i < num;i++){
if(num % i == 0)
return false;
}
return true;
}
我们来接着想一下,如果我们对一个数进行判断,最好情况下是被 2 整除后直接被判断为非素数,最坏情况下为遍历一遍判断为素数,所以在不考虑素数与非素数的个数占比的差异的情况下,我们可以大致认为平均下来时间复杂度为O(n/2).
对于一个自然数 n, 如果存在 a * b == n (a <= b),那么必定
存在以下结论:
在利用 for 循环进行遍历的时候,如果 3 可以将 12 整除 .那么,就可以认定 12 为 合数. 换一种思想,对于一个素数来讲,如果在(int)sqrt(n)+1 之前都没有 i 将其整除,那么之后的 i 也就不会有数据会将其整除,因为 如果 6 可以 将 12 整除, 那么 2 肯定也是可以的. 所以,对于 for 循环的迭代次数我们可以有理论依据的将其减少,得到以下的更高效率的代码
bool isPrime(int num){
for(int i = 2;i * i < num;i++){ // i <= (int)sqrt(num) + 1 也可
if(num % i == 0)
return false;
}
return true;
}
这个名词对于参加过一些程序设计比赛的同学应该不会陌生,所谓打表就是讲一些数据预先存起来,在程序运行的时候直接访问,得到一个O(1)的可观时间.
就拿我们这个判断素数来说吧,对于一个程序程序设计比赛来说,数据量是比较大的,如果我们在素数问题上一次又一次的判断,那么一般都会TLE的,因此我们引入了这样一个思想——>空间换时间,即使用一个数组来存储每个数的状态(是否为素数),这样就可以实现 O(1) 的时间复杂度了.
int isPrime[10] = {0,1,1,1,0,1,0,1,0,1}; //此处列出了0-9 十个数的素数状态
然而还有一个问题没有解决,对于几十几百的数,我们还是有那么一点点的精力来预先存储每个数的状态的,但对于很大的数据来说,我们还是束手无策的,因此,素数筛就排派上了很大的用场.素数筛有很多种,这里只给大家讲一种最基本的埃氏筛
思路引用了下面这篇博客,以下为核心思想:
从2开始 2是素数 那么4不是 6不是 8也不是 10、12、14、16、18、20 都不是 这是9次操作
然后 3 开始 6 9 12 15 18 都不是素数 这是5次操作
然后4 跳过 5 跳过 6 跳过
从7开始 14 不是素数 这是1次操作
后边的 8 9 10 11 12 14 15 16 18 20 都会跳过
而11 13 17 19 都不会操作 因为他们的倍数 大于20了
其中核心思想是如果一个数确定为素数,那么其倍数(2,3,4,…)都不会为素数!
废话不多说了,还是上代码吧~
// // Created by 29273 on 2020-07-26. // #include <iostream> #include <set> #include <unordered_map> #include <map> #include <cctype> #include <algorithm>m #include <string.h> #include <string> #include <vector> #include <cstdio> using namespace std; #define maxNum 10000 int prime[maxNum]; // 将素数从小到大存储起来 bool isPrime[maxNum]; // 存储每一个数 int countN; void Prime(int n){ //埃氏筛 countN = 0; for(int i = 2;i <= n;i++){ if(!isPrime[i]){ prime[countN++] = i; } for(int j = 2; j * i <= n;j++){ isPrime[j*i] = true; } } } int main(){ Prime(1000); for(int i = 0;i <= countN;i++){ printf("%d ",prime[i]); } return 0; }
相较于我们对每一个数通过函数进行判断然后存储状态的方法,在之前那篇博客中实验证明过,埃氏筛确实节省了很多的时间.
温馨提示:使用素数筛还是需要要看情况的,比如题目数据最大为1e6 ,那么我们的参数 maxNum 肯定是需要调整的,如果为 maxNum == 1e7 会造成不必要的时间浪费.
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。