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

http://www.cnblogs.com/rausen/p/4138233.html

#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;

}