【筛法求素数】【质因数分解】bzoj2721 [Violet 5]樱花

#include<cstdio>
#include<iostream>
using namespace std;
#define MOD 1000000007
int n;
bool Not[1000001];
int pr[1000001],e,ci[1000001];
void shai()
{
    Not[1]=1;
    for(int i=2;i<=1000;++i)
      if(!Not[i])
        for(int j=i*i;j<=1000000;j+=i)
          Not[j]=1;
    for(int i=1;i<=1000000;++i)
      if(!Not[i])
        pr[++e]=i;
}
long long ans=1;
int main()
{
    scanf("%d",&n);
    shai();
    for(int i=1;i<=n;++i)
      {
        int t=i;
        for(int j=1;j<=e&&pr[j]<=t&&Not[t];++j)
          while(t%pr[j]==0)
            {
              ++ci[pr[j]];
              t/=pr[j];
            }
        if(!Not[t])
          ++ci[t];
      }
    for(int i=1;i<=n;++i)
      ans=(ans*(long long)(ci[i]<<1|1))%MOD;
    cout<<ans<<endl;
    return 0;
}