Achieve Internet Interview Question
AnalystsTeam: artificial intelligence team
Country: United States
Interview Type: Written Test
/*
* isprime: given an odd number, check if it is prime.
*/
int
isprime(const unsigned int n)
{
assert(n >= 3);
assert(n % 2 == 1); /* odd */
/*
* going upto sqrt is sufficient, but sqrt is not easy to compute
* without using floating point.
*/
for (unsigned int d = 3; d < n/2; d += 2)
if (n % d == 0)
return 0;
return 1;
}
/*
* nextprime: find the next prime larger than n.
* Step up to successive odd numbers and test.
*/
unsigned int
nextprime(unsigned int n)
{
if (n == 0) /* 1 is neither prime nor composite */
return 2;
/* get the next odd number that is larger */
if (n % 2 == 0)
n++;
else
n += 2;
/* check each successive odd number */
while (1) {
if (isprime(n))
return n;
n += 2;
}
}
#include <iostream>
#include <sstream>
void usage(const char *pname){
std::cerr << "USAGE: " << pname << " <numbers>" << std::endl;
std::cerr << " where numbers is a list of n digits where 1 <= n <= 5 and each " << std::endl;
std::cerr << " each digit is > 0 and <=100" << std::endl;
}
int main(int argc, char *argv[]){
if (argc < 2 || argc > 6){
usage(argv[0]);
return -1;
}
int T = argc-1;
int *N = new int[T];
int max = 0;
for (int ii = 0; ii < T; ++ii){
std::stringstream ss;
ss << argv[ii+1];
ss >> N[ii];
max = max < N[ii]?N[ii]:max;
}
int nchecks = max*max + 1;
int *primes = new int[nchecks];
memset (primes, 0, sizeof(int)*nchecks);
// mark primes
primes[0]=1; // ignore 0
primes[1]=1; // ignore 1
for (int ii = 2; ii < nchecks; ++ii){
if (primes[ii])
continue;
for (int jj = ii+ii; jj < nchecks; jj += ii){
primes[jj] = 1;
}
}
int nprimes = 0;
for (int ii = 0; ii < T; ++ii){
for (int jj = N[ii]+1; jj < nchecks; ++jj){
if (!primes[jj]){
std::cerr << jj << std::endl;
break;
}
}
}
delete [] N;
delete [] primes;
return 0;
}
STOP POSTING YOUR FUCKING HOMEWORK.
- Anonymous December 10, 2013