## Interview Question

• 1
of 1 vote

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

1,000,000,000,039
...skipped 3612 lines...
1,000,000,099,841
---------------------
3,614,000,181,007,876

It takes 2 minute in my i5 PC.

Comment hidden because of low score. Click to expand.
0

I got same answer, in few seconds.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

Increment i by 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

``One mistake, It's "for(ulli i = 3; i <= res; i++)"``

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ;-)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.