数学:质数质数/素数:一个数除了1和它本身没有别的因数如何去求一个数是不是质数呢? 一般来说,只需要从2(1不是既不是质数也不是合数)开始遍历,一直到n - 1,如果 n % i 都不等于0,也就是说,2到n-1里面,每个数都与n去除,都肯定是有余数的,所以这个数一定是质数int main{ int n;cin>>n; int flag = 1; for(int i = 2; i 很明显,判断一个数是不是质数花费了n的时间可以很轻松的知道,除了2以外的偶数都不是质数,因为都可以被2整除,所以我们把只需要判断奇数就可以了,同时,如果一个数存在因数大于这个数的开方,也就是如果大于根号下这个数,那么一定是这个数本身,因为两个数相乘,最大也只有可能是根号n乘以根号n嘛,由此,我们需要花费的时间就只到根号n了if(n == 2)return true;if(n % 2 == 0)return false;for(int i = 3; i 如果一个数不是质数,那肯定可以表示成多个质数的乘积,因为无论什么除了质数的数外,它通过分解可以变成多个数相乘,如果这些因数还不是质数,同样可以被不断分解,我们写一个程序来把一个数分解成质因数相乘的形式#include using namespace std;int main{ int t;cin>>t; while(t --) { int n;scanf("%d",&n); for(int i = 2; i 1)cout 这题是acw算法基础课数学打卡的第二题,可以看到,我们从2开始遍历到根号n,有个疑问:它会遍历到4,6,8,9....的合成数,为什么这个程序可以正确执行呢?因为n被质数除了,也就是说,2肯定先被遍历,那么如果n 是 20,那么肯定会优先被除到5,它被除了2次2,也就是说,它不断的被质数除了,就不可能再被像4,6,8这些数除.现在,有这么一道题,让你判断1-n有多少个质数,用之前最朴素的想法,可以这么写int n;cin>>n;if( n == 1)cout const int N = 1e6+10;int q[N] {2};int cnt = 1;void prime(int n){ for(int i = 3; i >n; if(n == 1)cout 我的本意是每遇到一次质数,记录下来,和刚才那个方法一对比,甚至少过了一个数据听完课后,我才知道原来这么简单可以在O(nln(n))的时间复杂度下解决 :通过上面的思考,可以知道,(先假设开了一个布尔数组q,大小>=n)从小到大每遇到一个没见过的数(就是q[i]=false),就把这个数直到n的所有倍数设为true,同时res++;最后遍历到n的时候输出res就可以了#include using namespace std;const int N = 1e6+10;bool q[N];int res;void prime(int n){ for(int i = 2; i >n; prime(n); cout 为什么复杂度如此低?假设我们要把一个数设为true,那么这个数被质因数分解后,最大的因数有多大呢?答案很大概率上是非常小的,在绝大多数情况下,这个数在2,3,5就被设置为true了具体更加详细的原理解析,在oi-wiki上有,这里给出链接->Eratosthenes 筛法: #include using namespace std;const int N = 1e6+10;int primes[N],cnt;bool q[N];int res;void prime(int n){ for(int i = 2; i >n; prime(n); cout 在数据较小时,效果可能不明显,数据量足够时,速度相比上个算法快将近1倍现在,让我们好好回顾一下这个突如其来的算法(当然是因为课上讲的时候就是突如其来的啊),最里层的if(primes[j] == 0),只要它发生,就break,说明primes[j]就是i的最小质因子,因为很明显,primes存的就是质数,上面那一句就是这个算法它是如何筛数的q[...] = true,也就是说,i从2开始,质数的很大倍数就被筛了,比方说一个合数x,那么它肯定可以被分解出一个质因数,这个质因数乘以x另外一个因数的时候,x就被筛了,例如,9,3是质数,它首先被加入到primers中,每个质数乘以3说的可能不太清晰,让我们从新捋一遍摘要：数学:质数质数/素数:一个数除了1和它本身没有别的因数如何去求一个数是不是质数呢? 一般来说,只需要从2(1不是既不是质数也不是合数)开始遍历,一直到n - 1,如果 n % i 都不等于0,也就是说,2到n-1里面,每个数都与n去除,都肯定是有余数的,所以这
每个小于i的质数都开始从它本身乘以i了,例如从2开始,随着i的增加,2*2,2*3,2*4,2*5...都被筛了,同时,i到5的时候,primes也加入了3,5...它们共同开始质数筛选,3加入后,有开始了3*3,3*4....的筛选,5也同理,但是它是从5*5开始(5*2,5*3...已经被2*5,3*5...筛选了),所以这个算法很大程度避免了像6=2*3,被2和3同时筛选的重复情况,此算法复杂度好像是nloglogn
来源：真来教育
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!