Interview Question
Country: United States
bool isPrime(int n){
if(n == 0 || n == 1)
return false;
if(n == 2)
return true;
if(n%2 == 0)
return false;
double squared = sqrt(n);
int res = floor(squared);
for(int i = 3; i < res; i++){
if(n%i == 0)
return false;
}
return true;
}
int main(){
ulli res = 0;
for(ulli i = 1000000000000; i < 1000000100000; i++){
if(isPrime(i)){
res += i;
}
}
cout<<res;
}
Answer: 3,614,000,181,007,876
This C++ code will run in few seconds to get the answer (3 seconds on my i7 PC):
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
//Shortcuts for laziness:
#define FOR(i,s,e) for(int (i) = (s); (i) < (e); ++(i))
#define REP(i,n) FOR(i,0,n)
#define lli long long int
const int MILLION = 1000010;
bool Sieve[MILLION];
vector<int> Primes; // list of primes less than 1M;
int N; // number of primes less than 1M;
void sieve(){
int n = sqrt(MILLION) +1 ;
REP(i, MILLION) Sieve[i] = true;
Sieve[0] = Sieve[1] = false;
FOR(i,2,n) if (Sieve[i])
for(int j = i*i; j< MILLION; j+=i)
Sieve[j] = false;
FOR(i,2,MILLION)
if (Sieve[i]) Primes.push_back(i);
N = Primes.size();
//FOR(i,2, 100) cout <<Primes[i] % 6<< " "; cout<<endl;
return;
};
bool is_Prime(lli x){
REP(i, N) if (x % Primes[i] == 0) return false;
return true;
}
int main()
{
sieve();
lli sum = 0;
lli LO = 1000000000000;
lli HI = 1000000100000;
lli k0 = LO/6;
lli x = 6*k0+1;
while(x<HI-6){
if (is_Prime(x)) sum+= x;
x+=4;
if (is_Prime(x)) sum+= x;
x+=2;
}
cout <<sum<<endl;
return 0;
}
It is just a segment prime seive
typedef long long ll;
bool is_prime_aux[1000001];
bool is_prime[100001];
ll segment_seive(ll a, ll b)
{
for (ll i = 0; i * i <= b; ++i) is_prime_aux[i] = true;
for (int i = 0; i <= b - a; ++i) is_prime[i] = true;
for (ll i = 2; i * i <= b; ++i)
{
if (is_prime_aux[i])
{
for (ll j = 2 * i; j * j <= b; j += i) is_prime_aux[j] = false;
for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) is_prime[j - a] = false;
}
}
ll sum = 0;
for (int i = 0; i <= b - a; ++i) sum += is_prime[i] ? a + i : 0;
return sum;
}
The sum of prime numbers in the original range is given as 6,000,292.
The new range is a thousand (10^3) times larger and its starting point is a million (10^6) times higher.
So the sum of primes in the new range should be approximately 10^9 times the original sum, so about ~ 6 * 10^15.
That took about 5 seconds on my iBrain (faster than i7 ;-)
1,000,000,000,039
- kyduke April 29, 2015...skipped 3612 lines...
1,000,000,099,841
---------------------
3,614,000,181,007,876
It takes 2 minute in my i5 PC.