CareerCup

STOP POSTING YOUR FUCKING HOMEWORK.

/*
 * 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;
}

Sorry, the "mark primes" comment should read "mark non primes" and nprimes was a debugging thing I left in there by accident