质因数欧拉线筛变形

题目：

质因数

(prime.cpp/in/out 1s 128M)

OtosakaYuu最近为了Nao Tomori拯救世界而立了一个flag，于是他想了一道数学题。有一个正整数数列a1,a2…an。定义函数f(x)为x的不同的质因数数量。球f(a1),f(a2)…f(an)。

Input

第一行包含一个正整数，表示n。

接下来n行，每行包含一个正整数ai。

1<=n<=1000000,2<=ai<=1000000

Output

输出n行，第i行输出f(ai)。

Sample Input

30030

2333

Sample Output

【样例说明】

12=2×2×3；

30030=2×3×5×7×11×13；

2333是一个质数。

code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e6+15;
 4 int n;
 5 int prime[maxn],inprime[maxn],a[maxn];
 6 inline int read(){
 7     int x=0,f=1;char ch=getchar();
 8     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
 9     while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
10     return x*f;
11 }
12 void work(){
13     memset(inprime,1,sizeof(inprime));
14     for (int i=2;i<=maxn;i++)
15         if (inprime[i])
16         {
17             for (int j=i;j<=maxn;j+=i)   prime[j]++;
18             for (int j=i;j<=maxn/i;j++) inprime[i*j]=0;
19         }
20 }
21 int main()
22 {
23     n=read();
24     for (int i=1;i<=n;i++)   a[i]=read();
25     work();
26     for (int i=1;i<=n;i++)   printf("%d\n",prime[a[i]]);
27     return 0;
28 }

质因数 欧拉线筛变形

相关推荐

质因数欧拉线筛变形