Skip to content

Instantly share code, notes, and snippets.

@knotman90
Last active February 14, 2017 11:40
Show Gist options
  • Save knotman90/b7a18b887f74ff92e643eae96055e9eb to your computer and use it in GitHub Desktop.
Save knotman90/b7a18b887f74ff92e643eae96055e9eb to your computer and use it in GitHub Desktop.
#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----
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment