## Google Interview Question

Software Engineer / Developers**Country:**United States

he said multiples of 6 +/- 1, all the primes you listed fit that criteria. 41 = 42 -1 ; 43 = 42 + 1; 47 = 48 - 1; 53 = 54 - 1 and so forth...

I doubt if this would make the answer.

i) "From then on check if no-1 no+1 is prime" : this is not trivial. If this was fine, than we could just check for all digits larger than 100..0 which would be only take x3 amt of time.

ii) I interpret "10 digit number" as "a very large number". Also note multiplication/division/sqrt is very expensive. So I would prefer a solution that does not involve mult/div/sqrt and large amt of memory.

The best I can think of is a "lazy" version of sieve of Eratosthenes where the end of sieve may move with delayed sieving. But still this would require remembering all previously found primes.

The mentioned answer seems not applicable for all the numbers.

Number 49 is not prime but as per the logic mentioned in the answer it should be prime.

So the answer is wrong.

@Aakash, he never said it's applicable to all numbers, he said generate numbers in the form of 6k - 1 and 6k + 1 and then CHECK if they are prime, so there is a primality test involved for each number generated. Even though such a test becomes non-trivial for numbers with 8-9+ digits, it's still a solid answer IMO.

Not all primes are in the form of 6n+1 and 6n-1. This holds true up to a certain digits, but definitely not 10 digits:

```
1,000,000,000 / 6 = 166,666,666 (integer division)
166,666,666 * 6 = 999,999,996
999,999,996 + 6 = 1,000,000,002
when n = 166,666,667
6n-1 = 1,000,000,001
6n+1 = 1,000,000,003
Both 1,000,000,001 and 1,000,000,003 are not prime:
1,000,000,001 = 1,001×999,001
However when when n = 166,666,668
6n-1 = 1,000,000,007
6n+1 = 1,000,000,009
Which are both prime.
```

In conclusion, this method of generating primes holds true for most integer "n", but not always.

@oOZz: wrong, all PRIMES are in the form of 6n-1 or 6n+1 but not all numbers in the form of 6n-1 or 6n+1 are not PRIME.

Proof:

Checking a million primes is certainly energetic, but it is not necessary (and just looking at examples can be misleading in mathematics). Here is how to prove your observation: take any integer n greater than 3, and divide it by 6. That is, write

n = 6q + r

where q is a non-negative integer and the remainder r is one of 0, 1, 2, 3, 4, or 5.

If the remainder is 0, 2 or 4, then the number n is divisible by 2, and can not be prime.

If the remainder is 3, then the number n is divisible by 3, and can not be prime.

So if n is prime, then the remainder r is either

1 (and n = 6q + 1 is one more than a multiple of six), or

5 (and n = 6q + 5 = 6(q+1) - 1 is one less than a multiple of six).

Remember that being one more or less than a multiple of six does not make a number prime. We have only shown that all primes other than 2 and 3 (which divide 6) have this form.

@Up

Easy tiger :) that's what i meant, sorry for the bad wording, but it's clear from the example that I gave, isn't it?

The point is this method is not accurate. This 6n+/-1 formula is like saying "pick an odd number", because all the primes are odd, but in fact not all the odd number are primes.

Haha sorry, I didn't mean to come off as angry :) I just wanted to make it clear that we were talking about primes and non-primes hence the capitalization. We could generate all 6n-1, 6n+1 numbers that are 10 digits and do a primality test on them but that would not be an optimal solution.

I suggested using the sieve of eratosthenes to generate all 10 digit primes as they are considered "small" relative to the 100+ digit primes used in real-world applications and would take linear time to generate with some optimizations done to the algorithm.

How would you check if 6n +/- 1 is prime or not? If there is a easy way to do it then we would as well incrementally check all the numbers above 1000000000 to be prime or not. What this 6n is doing is just skipping to every sixth number.

Nice one, Phoenix! I had the same idea. If you eliminate the prime factors of 6, which are 2 and 3, then you can expand on that idea for all numbers. Here is the sequence of all prime numbers. Unfortunately, this sequence is infinite, so let's only take a few primes at a time, okay? :)

```
static IEnumerable<int> FindPrimes(int lower, int count)
{
var primes = from n in Sequence(lower)
where n == 2 || n % 2 != 0
where n == 3 || n % 3 != 0
where n >= 2
where !Enumerable.Range(1, n)
.Where(k => 36 * (long)k * k - 12 * k < n)
.Any(k => n % (6 * k + 1) == 0 || n % (6 * k - 1) == 0)
select n;
return primes.Take(count);
}
```

In this code "lower" is the start of where we look for prime numbers. The parameter "count" specifies how many prime numbers we want.

Oh, almost forget. I chose a generator to get the sequence started:

```
public static IEnumerable<int> Sequence(int start)
{
for (int i = start; ; i++) yield return i;
}
```

Or you can simply return the entire sequence of prime numbers and take as many as you want! (or as many as your memory allows you)

Oops! Did you ask for primes larger than a billion?

Well ... this LINQ mess above won't cut it today then. We should probably implement a version of the Miller-Rabin primality test and eliminate numbers through the use of witnesses. I don't think I want to implement Miller-Rabin again. I'm sure there are enough implementations floating around.

Actually ... I thought about it some more and thought to myself that the runtime of finding primes in that range shouldn't be as bad as my tests showed. My LINQ code is just horrible. If you unroll the mess above, the following runs just fine:

```
static bool IsPrime(int n)
{
if (n != 2 && n % 2 == 0) return false;
if (n != 3 && n % 3 == 0) return false;
for (int k = 1; 36 * k * k - 12 * k < n; ++k)
if (n % (6 * k + 1) == 0 || n % (6 * k - 1) == 0)
return false;
return true;
}
```

Let this be the driver:

```
int count = 3;
for (int i = 1000000000; ; i++)
{
if (IsPrime(i)) count--;
if (count == 0) break;
}
```

That runs within a second on my i7 and we didn't even need Miller-Rabin! Apologies. I am apparently running out of coffee. And no more LINQ for me today.

BTW, first three prime are: 100000007, 1000000009, 1000000021. The next three are 1000000033, 1000000087, 1000000093 - if you want to check your solution some more.

Aww man :( I'm really not paying attention anymore. Now I haven't even made use of Phoenix's suggestion to only look at numbers adjacent to multiples of six! Please give me another chance to fix this:

```
int n = 1000000000 - 1;
while (n % 6 != 0) n++;
int count = 3;
var primes = new List<int>();
for (; n < int.MaxValue; n += 6)
{
if (IsPrime(n + 1)) { primes.Add(n + 1); count--; }
if (IsPrime(n - 1)) { primes.Add(n - 1); count--; }
if (count == 0) break;
}
```

Pay attention to subtracting one from the start value, because it could lay just above a multiple of six. The code above looks for the first number divisible by six and then goes in steps of six to check primes. Actually ... if we want to make this effort and go in steps of six to eliminate candidates, maybe we should go all the way and rather eliminate numbers through Miller-Rabin after all ... not sure anymore.

BTW, why do people on here claim that a primality test for that number range is non-trivial? Is there an error in my solution? It appears to run just fine and I have just generated the first 300 prime numbers above a billion. Can you explain why you thought it is non-trivial or has my solution (or non-solution depending on your answer) refuted that claim already?

Brute force solution: check every number begin from 1 000 000 000 by dividing on every integer from 2 to sqrt(n).

```
void print_5_primes_10_digit() {
for (int prime = 1000000000, count = 0; count < 5; prime++) {
bool is_prime = true;
for (int divisor = 2; divisor <= std::sqrt(prime); divisor++) {
if (prime % divisor == 0) {
is_prime = false;
break;
}
}
if (is_prime) {
printf("%d\n", prime);
count++;
}
}
}
```

It runs 0.006 sec on my computer.

```
1000000007
1000000009
1000000021
1000000033
1000000087
```

You can initiate prime to 1 million +1 and then increment by two since even numbers won't be prime.

There is some optimization even for brute force: memorize prime numbers and for the next number (K) to check we could check if the number is divisible by those early memorized prime numbers only (not all the numbers from 2 to Sqrt(K)).

And there is another pretty simple and efficient algorithm to compute prime numbers: check sieve of Eratosthenes algorithm.

```
def specificPrimes():
from math import pow
primes = []
for i in range(2, 10**5):
isPrime = True
for j in primes:
if pow(j, 2) > i:
break
elif i % j != 0:
isPrime = False
break
if isPrime:
primes.append(i)
largePrimes = []
for i in range(10**9, 10**10):
if len(largePrimes) == 10:
break
isPrime = True
for j in primes:
if pow(j, 2) > i:
break
elif i % j != 0:
isPrime = False
break
if isPrime:
largePrimes.append(i)
return largePrimes
```

This one's pretty straightforward. Get all the primes up til the square root of 10,000,000,000 (11 digits), and use those primes to find the first 10 primes above 1,000,000,000 (10 digits).

```
/*
Write a method to return first five 10 digit prime numbers.
*/
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric> // std::accumulate
#include <sstream>
#include <stack>
#include <string>
using namespace std;
vector<int> vecPrimeTable;
int nPrimeTableMax = 0;
class Solution
{
public:
static inline bool IsPrime( int nInt )
{
int nSqrt = static_cast<int>( sqrt( nInt * 1.0 ) );
if ( nSqrt > nPrimeTableMax )
CalculatePrimeTable( static_cast<int>( nSqrt * 1.1 ) );
for ( vector<int>::iterator ii = vecPrimeTable.begin(); ii != vecPrimeTable.end(); ii ++)
{
if ( *ii > nSqrt )
break;
if ( nInt % *ii == 0 )
return false;
}
return true;
}
static void CalculatePrimeTable( int nIntMax )
{
if ( 0 == vecPrimeTable.size() )
vecPrimeTable.push_back( 2 );
int nIntMin = vecPrimeTable[ vecPrimeTable.size() - 1 ] + 1;
if ( nIntMin % 2 == 0)
nIntMin ++;
for ( int i = nIntMin; i <= nIntMax; i += 2)
{
if ( IsPrime( i ))
vecPrimeTable.push_back( i );
}
nPrimeTableMax = max( nPrimeTableMax, nIntMax );
}
static std::vector<int> OutputFirstNPrime( int nBegin, int nCount )
{
std::vector<int> vecResult;
//CalculatePrimeTable( static_cast<int>( sqrt( nBegin * 1.1 ) ) );
int nValue = nBegin;
if ( 0 == nBegin % 2 )
nValue ++;
while ( nCount >= 0 )
{
if ( IsPrime( nValue ))
{
vecResult.push_back( nValue );
nCount --;
}
nValue += 2;
}
return vecResult;
}
static void OutputArray( int A[], int n)
{
std::cout << n << std::endl;
for ( int ii = 0; ii < n; ii ++ )
if ( ii < n - 1 )
std::cout << A[ii] << ",";
else
std::cout << A[ii];
std::cout << std::endl;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<int> vecResult = Solution::OutputFirstNPrime(1000000000, 10);
copy( vecResult.begin(), vecResult.end(), ostream_iterator<int>(cout, " "));
_getch();
return 0;
}
```

Phoenix's answer is sound logic but we can also use the sieve of Eratosthenes to generate all primes up to 10,000,000,000 (11 digits), mind you primes up to 11 digits are considered very small primes in contrast to the primes used in current applications (such as cryptographic algorithms) so the sieve is a good and efficient way to generate the first 5, 10 digit primes in linear time.

Link for those interested: en.wikipedia.org/wiki/Sieve_of_Eratosthenes

I recall seeing this before. The same link also says this:

"The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so)" - that is only 7 0's or 8 total digits. It doesn't say anything about 11 digits.

Keeping this in mind, will the sieve really be that much better than Phoenix's method?

Yes Wikipedia says 10 million (7-8 digits) but mind you that small prime numbers in the real world are considered those numbers that are ~20 digits as most real-world applications use 100+ digit primes for their algorithms, so 11 digits is relatively small compared to what is being used today.

That being said, the sieve of eratosthenes is obviously not guaranteed to produce a better result than Phoenix's answer, but as some of the replies suggested to his answer not every number in the form of 6k -1 or 6k + 1 is prime (high chance you can get a false positive, i.e the number 49 = 48 + 1 = (6*8) + 1)

The sieve is guaranteed to generate all primes up to N, and with further optimizations it can do it in linear time. There are better and faster sieves one can use to generate primes but they are not as simple to understand as the sieve of eratosthenes like the sieve of Atkin.

All in all, I think this question is a good way to discuss different methods of generating primes and the trade-offs from using one method over the other. It's a good question that probes the logic of the candidate, but can also be considered a complete curve ball if the candidate is not aware that all primes after 3 are in the form of 6k+1 or 6k-1.

Anyways, I'm going off track :) Hope to see some more creative answers to this question

I think the key to this question is to use dynamic programming to save all the prime number as we calculate all the prime

```
import math
primelist = [2]
def isprimeinlist(input):
mid = math.sqrt(input)
for i in primelist:
if i <= mid and input%i == 0:
return False;
return True;
def checkprime(input):
mid = math.sqrt(input)
start = 0
for i in primelist:
start = i
if i <= mid and input%i == 0:
return False
while start <= mid:
if (input % start) == 0:
return False
if start == 2:
start += 1
else:
start +=2
if isprimeinlist(start):
primelist.append(start)
return True
checking = 0
for i in range(1000000,10000000):
if checkprime(i):
print '{} is prime'.format(i)
checking += 1
if checking == 5:
break
print primelist
```

```
public static void firstKNDigitsPrime(int k, int n)
{
double power10n = Math.pow(10, n);
// System.out.println("10^n: " + power10n);
int minCoff = (int) ((power10n + 1) / 6);
int number = 6 * minCoff + 1;
int count = 1;
for (int i = 2; i < Math.sqrt(number); i++)
{
if (number % i == 0)
{
count = 0;
break;
}
}
minCoff++;
while (count < k)
{
int sixnminusone = minCoff * 6 - 1;
int sixnplusone = minCoff * 6 + 1;
// System.out.println("6n - 1: " + sixnminusone);
// System.out.println("6n + 1: " + sixnminusone);
boolean isSixNMinusOnePrime = true;
boolean isSixNPlusOnePrime = true;
for (int i = 2; i <= Math.sqrt(sixnminusone); i++)
{
if (sixnminusone % i == 0)
{
isSixNMinusOnePrime = false;
break;
}
}
for (int i = 2; i <= Math.sqrt(sixnplusone); i++)
{
if (sixnplusone % i == 0)
{
isSixNPlusOnePrime = false;
break;
}
}
if (isSixNMinusOnePrime && count < k)
{
System.out.println(count + 1 + ": " + sixnminusone);
count++;
}
if (isSixNPlusOnePrime && count < k)
{
System.out.println(count + 1 + ": " + sixnplusone);
count++;
}
minCoff++;
}
}
```

This solution is based on eratosthene's sieve. Algorithm is this

-Find all primes upto SQRT(1billion) using sieve.

-check divisibility of numbers starting after 1 billion with all the primes calculated above until 5 primes are found.

It ran in about 20 ms on my laptop.

**Edit - I ran the brute force solution and it is faster than the sieve method. I guess it is because brute force does not need any storage.

```
public static void find5PrimesfromN() {
long IN = 1000000000l;
int N = (int)Math.sqrt(IN)+1;
boolean[] nonprime = new boolean[N];
int d=2;
while(d < (int)Math.sqrt(N)+1) {
for(int i=d+1; i<=N; i++) {
//System.out.println("compare");
if(i%d == 0) {
nonprime[i-1] = true;
}
}
d++;
for(int k=d; k<N; k++) {
if(!nonprime[k-1]) {
d = k;
break;
}
}
}
List<Integer> primesUpSqRoot = new ArrayList<>();
for(int k=2; k<N; k++) {
if(!nonprime[k-1]) {
primesUpSqRoot.add(k);
}
}
long p = IN+1;
int np = 0;
while(np < 5) {
boolean isP = true;
for(int div : primesUpSqRoot) {
if(p%div == 0) {
isP = false;
break;
}
}
if(isP) {
System.out.println("prime "+p);
np++;
}
p++;
}
}
```

Primes after a point in the series are multiples of 6 +/-1. that is 31 = 30 + 1, 37 = 36 + 1 and so on.

- Phoenix July 23, 2014So find the first number in 10 digits that is divisible by 6 and then from then on check if no-1 or no+1 is prime. increment by 6 and do the same check until the prime count = 5