ProjectEulerProblem#187.cpp

#include <bits/stdc++.h>

#include <gmpxx.h>
#include <functional>
#include <numeric>

//TYPEDEFS
typedef unsigned long long ull;
typedef signed long long ll;



void getPrimesSieve(vector<long long>&primes, const ll n) {
    vector<bool> nums(n+1,true);
    primes.push_back(2);
    for(ll i=3; i*i<n+1; i+=2) {
        if(nums[i]) {
            for(ll j=i*i; j<n+1; j+=2*i) {
                nums[j]=false;
            }
        }
    }
    for(ll i =3 ; i <=n ; i+=2)
        if(nums[i])
            primes.push_back(i);
}

//problem 187----
void solve187(){
    constexpr const ull LIM = 100000000;
    constexpr const ull LIMP = LIM/2;
    ull ans=0;
    vector<ll> primes;    
    getPrimesSieve(primes,LIMP); //primes up to LIMP
    for(int i=0;i<primes.size() ; i++){
        const ull pl = LIM/primes[i];
        auto p = upper_bound(ALL(primes) , pl);
        p--;
        if(*p >= primes[i]){
            auto dist = abs(distance(p,primes.begin()+i))+1;
            ans+=dist;
        }
    }
    cout<<ans<<endl;
}
//end of problem 187----