|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <iostream> #include <vector> #include <map> #include <stdio.h> using namespace std; int prime[1000001]; int primes[1000001]; double dp[1000001]; vector<int> vb; map<int,int> mp; int main() { int n,t; primes[0]=primes[1]=0; for(int i=2;i*i<1000001;i++) { if(prime[i]==0) { for(int j=i*i;j<1000001;j+=i) { prime[j]=1; primes[j]=i; } //primes[i]=i; } } prime[0]=prime[1]=0; for(int i=2;i<1000001;i++) { if(primes[i]==0) primes[i]=i; if(prime[i]) prime[i]=0; else prime[i]=1; prime[i]+=prime[i-1]; } dp[1]=0; for(int i=2;i<1000001;i++) { int k=i; mp.clear(); vb.clear(); while(primes[k]!=0) { if(mp[primes[k]]==0) { mp[primes[k]]=1; vb.push_back(primes[k]); } k/=primes[k]; } double g=0; for(int j=0;j<vb.size();j++) g+=dp[i/vb[j]]; dp[i]=(g+prime[i])/vb.size(); } cin>>t; int c=0; while(t--) { cin>>n; //cout<<prime[n]<<"\n"; c++; cout<<"Case "<<c<<": "; printf("%.10lf\n",dp[n]); } return 0; } |