Hello,
I am trying to solve this problem and getting TLE, and I think my code is the best I can do. Please help me solve the problem by any efficient idea or optimizing my code:
#include <bits/stdc++.h>
using namespace std;
#define MX 5000005
#define M 100000007
#define LL long long
#define dbg(x) cout<<#x<<" = "<<x<<"\n"
int n;
LL cnt[MX];
int b[MX];
int main(){
while(cin>>n){
if(n==0) break;
memset(b,0,sizeof(b));
for(int i=n,v=1;i>1;i--,v++){
cnt[i]=v;
}
for(int i=2;i<=n;i++){
if(b[i]==0){
for(int j=i*2;j<=n;j+=i){
b[j]=1;
int t=j;
int div=0;
while(t%i==0){
div++;
t/=i;
}
cnt[i]+=cnt[j]*div;
}
}
}
LL ans=1;
for(int i=2;i<=n;i++){
if(b[i]==0){
ans=(ans*(cnt[i]+1))%M;
}
}
printf("%lld\n",ans);
}
}