考察:质数筛
错误思路:
用Map可以很方便地合并同类项,但是用Map会MLE
正确思路:
对于1~n的每1个数,它们都会被它的最小质因数筛掉.这道题不是求分解n的质数,不能只枚举到√n.因为1~n之间还存在着质数.这些质数能够除尽>√n的质数
用筛法求出质数后.可以发现1~n的能够分解出质数p的个数是[n/p]个.这个可以分类讨论.实在不懂可以看y总视频.如果n还能除尽p^2.那么在p的基础上再求一次能除尽p^2的个数即可.因为除尽p的已经算了一次,所以求p^2的时候不需要*2
关于筛法.里层循环的=号非常重要.因为存在N/i=2.2而prime[j]==2的情况,如果没有等号就会少筛
1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 using namespace std; 5 typedef pair<int,int> pii; 6 const int N = 1000010; 7 int prime[N],cnt; 8 bool st[N]; 9 vector<pii> v; 10 void prework(int n) 11 { 12 for(int i=2;i<=n;i++){ 13 if(!st[i]) prime[cnt++] = i; 14 for(int j=0;prime[j]<=n/i;j++){ 15 st[i*prime[j]] = 1; 16 if(i%prime[j]==0) break; 17 } 18 } 19 } 20 void solve(int n) 21 { 22 for(int i=0;i<cnt;i++) 23 { 24 int ans = 0,t = n; 25 while(t) ans+=t/prime[i],t/=prime[i]; 26 printf("%d %d\n",prime[i],ans);//没必要判断ans是否为0,求出1~n的质数,质数也在里面 27 } 28 } 29 int main() 30 { 31 int n; 32 scanf("%d",&n); 33 prework(n); 34 solve(n); 35 return 0; 36 }