「オイラープロジェクト351~360」の編集履歴(バックアップ)一覧に戻る
#include<stdio.h> #include<vector> #include<iostream> #include<time.h> const int up=10000; std::vector<int> sosuu; bool so[up+1]; void setSo(){ int i2; memset(so,true,sizeof(so)); so[0]=so[1]=false; for(int i=4;i<=up;i+=2)so[i]=false; sosuu.push_back(2); for(int i=3;i<=up;i+=2){ if(so[i]==false)continue; sosuu.push_back(i); i2=i*2; for(int j=i*3;j<=up;j+=i2){ so[j]=false; } } } __int64 phi(__int64 n){ double re=n; for(int i=0;i<sosuu.size()&&sosuu[i]*sosuu[i]<=n;i++){ __int64 p=sosuu[i]; int count=0; while(n%p==0){ n/=p; count++; } if(count>0)re*=(1-1.0/p); } if(n!=1)re*=(1-1.0/n); return (__int64)re+0.5; } int main(){ double start=clock(); setSo(); __int64 size=10000*10000; __int64 ans=6*(size-1),t; for(__int64 i=2;i<=size;i++){ t=i-phi(i)-1; ans+=t*6; if(i%10000==0)std::cout<<i<<" "<<ans<<"\n"; } std::cout<<ans<<"\ntime="<<clock()-start; }