We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I was looking my code for many minutes only to realize that I forgot to substract 1 because of the condition of < N xD Anyway, I used Meissel-Lehmer algorithm to solve this, pretty simple if you already have a function to compute pi(n) efficiently:
#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;#define N 100000005#define limit 1000005vector<int>pi_sieve(limit);vector<int>prime_sieve(){bitset<limit>sieve;vector<int>ans;for(inti=2;i<limit;i++){if(!sieve[i]){pi_sieve[i]=pi_sieve[i-1]+1;ans.push_back(i);for(llj=1LL*i*i;j<limit;j+=i)sieve[j]=1;}elsepi_sieve[i]=pi_sieve[i-1];}returnans;}vector<int>primes;map<pair<ll,ll>,ll>phi_cache;llphi(llx,lla){pair<ll,ll>values={x,a};if(phi_cache.find(values)!=phi_cache.end())returnphi_cache[values];if(a==1)return(x+1)/2;llans=phi(x,a-1)-phi(x/primes[a-1],a-1);phi_cache[values]=ans;returnans;}map<ll,ll>pi_cache;llpi(llx){if(x<limit)returnpi_sieve[x];if(pi_cache.find(x)!=pi_cache.end())returnpi_cache[x];inta=pi((int)(pow(x,1.0/4)));intb=pi((int)(sqrt(x)));intc=pi((int)(pow(x,1.0/3)));llans=phi(x,a)+1LL*(b+a-2)*(b-a+1)/2;for(inti=a+1;i<b+1;i++){llw=x/primes[i-1];ans-=pi(w);if(i<=c){llb_i=pi((int)(sqrt(w)));for(intj=i;j<b_i+1;j++)ans=ans-pi(w/primes[j-1])+j-1;}}pi_cache[x]=ans;returnans;}intmain(){primes=prime_sieve();intt;cin>>t;while(t--){intn;cin>>n;longlongans=0;for(inti=0;i<primes.size();i++){intp=primes[i];if(1LL*p*p>=n)break;ans+=pi((n-1)/p);ans-=pi(p-1);}cout<<ans<<'\n';}return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #187: Semiprimes
You are viewing a single comment's thread. Return to all comments →
I was looking my code for many minutes only to realize that I forgot to substract 1 because of the condition of < N xD Anyway, I used Meissel-Lehmer algorithm to solve this, pretty simple if you already have a function to compute pi(n) efficiently: