In many programming competitions, we are asked to find (or count the number of) Prime Factors of an integer i. This is boring. This time, let’s count ...
In many programming competitions, we are asked to find (or count the number of) Prime Factors of an integer i. This is boring. This time, let’s count the number of Non-Prime Factors of an integer i, denoted as NPF(i).
For example, integer 100 has the following nine factors: {1,2,4,5,10,20,25,50,100}. The two which are underlined are prime factors of 100 and the rest are non-prime factors. Therefore, NPF(100) = 7.
Input
The first line contains an integer Q (1≤Q≤3⋅10^6) denoting the number of queries. Each of the next Q lines contains one integer i (2≤i≤2⋅10^6).
Output
For each query i, print the value of NPF(i).
Warning
The I/O files are large. Please use fast I/O methods.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 100 13 12 2018 |
7 1 4 2 |
題目大意：第一行給一個Q，代表Q次查詢，接下來Q行，每行一個整數i，求NPF（i）
拿樣例100來說，100的因數有（1,2,4,5,10,20,25,50,100）共9個，其中2和5是質數（一個大於1的自然數，除了1和它本身外，不能被其他自然數整除），應去掉，剩下7個。
所以NPF（100）= 7
拿樣例13來說，13的因數有（1,13）共2個，其中13是質數，去掉後，剩下1個。
所以NPF（13）= 1
解題思路：1.先預處理出1-2*10^6的質數。可以用eratosthenes篩法，時間複雜度O(NloglogN)（某位網友說的）
2.預處理答案，先看代碼：
for(int i = 1; i <= 2000000; ++i){ int rt = 2000000/i; for(int j = i; j <= rt; ++j){ if(vis[i]){//非質數 ++ans[i*j]; } if(vis[j] && i!=j){ ++ans[i*j]; } } }
第一個for迴圈，表示1到2*10^6的數。
第二個for迴圈，對於當前的數i，對 i 到 i*rt 進行處理
舉個慄子，對於100來說，ans【100】初始化是0
第一個迴圈到1時，
在第二個迴圈中：判斷1是非質數，第一個if中必然會有1*100=100，即ans【100】++；（100<rt,必然出現）
第二個if中會出現j=100，100是非質數，又100*1=100，即ans【100】++；
tip：當i=100時，j 從100開始累加而且 j 不會回溯，所以100=1*100這一種分解方法會在i=1的時候處理出來
即ans【100】+=2；
第一個迴圈到2時：
在第二個迴圈中：第一個if 判斷2是質數，跳過（相當於把2這個因數剔除了，即沒有加入答案中）
第二個if j=50時,50是非質數，又50*2=100，所以ans【100】++；
第一個迴圈到4時：
在第二個迴圈中：第一個if 判斷4是非質數，4*25=100,ans【100】++；
第二個if j=25時,25是非質數，25*4=100，所以ans【100】++；
第一個迴圈到5時：
在第二個迴圈中：第一個if 判斷5是質數，跳過，
第二個if j=20時,20是非質數，20*5=100，所以ans【100】++；
第一個迴圈到10時：
在第二個迴圈中：第一個if 判斷10是非質數，10*10=100，ans【100】++；
第二個if j=10時,10是非質數，但是i=j，跳過（相同因數處理一次即可，在第一個if處理了）
第一個迴圈到20時：20*5=100，但是5不會出現，因為j是從20開始不斷累加，ans【100】已經處理結束了，從上面分析可以看出ans【100】=7；
類似的，每個答案都可以在這2個迴圈中處理出來。
時間上：當i=1來說，rt=2*10^6，j會從1加到2*10^6
當i=2，rt=10^6， j會從2加到10^6；
......
當i=10，rt=2*10^5，j會從10加到2*10^5（此時數量級已經降了一級）
...
當i=100，rt=2*10^4，j會從1加到2*10^4
....
當i=1000，rt=2*10^3，j會從1000加到2000（共1000次）
.....
當i=sqrt（2*10^6） rt=i，第二層迴圈直接跳過，後面一樣，都是1次
把它們加起來，大概也就10^7左右（目測估計法算的）
預處理10^6左右，Q個問題3*10^6，加起來數量級也在10^7
某位大佬說10^7的數量級一般都能在1s跑完，要看測評機
一開始我是對每次枚舉每個數的因數（1-sqrt（n）），然後想辦法優化，結果都是超時....（(╯‵□′)╯︵┻━┻）
啟示：優化的時候想想辦法讓回溯的次數少一點。
AC代碼：
#include <iostream> #include <stdio.h> #include <cmath> using namespace std; bool vis[2000005]; int ans[2000005]; void init() { //開始篩，vis=1表示該數不是質數 vis[1]=1; int m=sqrt(2000002+0.5); for(int i=2;i<=m;++i) if(!vis[i]) for(int j=i*i;j<=2000002;j+=i) vis[j]=1; //篩選結束 for(int i = 1; i <= 2000000; ++i){ int rt = 2000000/i; for(int j = i; j <= rt; ++j){ if(vis[i]){//非質數 ++ans[i*j]; } if(vis[j] && i!=j){ ++ans[i*j]; } } } } int main() { init(); int Q; scanf("%d",&Q); while(Q--) { int n; scanf("%d",&n); printf("%d\n",ans[n]); } return 0; }
