## Interview Question

## Interview Answer

5 Answers

This solution can be optimized further. No need to check for even numbers (except 2, 2 is the only prime even number). You can find if 'n' is prime when it is not divisible by any number between 2 to n/2. More optimizaton can be achieved if the range is reduced further from 2 to sqrt(n). But finding a sqrt will be tedious and might require inclusion of math.h library.

there is a much more optimal solution, think about what you already know ;-) of course if this was an interview this would be my answer too (unless they asked for more performance.)

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes {{{ void sievePrime(int n) { // initialize array bool *sieve = (bool *)malloc(sizeof(bool) * (n+1)); for (int i = 0; i <= n; i++) { if (i < 2) sieve[i] = false; else sieve[i] = true; } for (int i = 2; i * i <= n; i++) { int k = i * i; while (k <= n) { sieve[k] = false; k += i; } } for (int i = 0; i <= n; i++) { if (sieve[i]) printf("%d\n", i); } free(sieve); } }}}

void printPrimes (int N) { int i; int * isNotP = malloc(sizeof(int) * N); if (isNotP == NULL) return; if (N < 2) { printf("Error in input %d\n", N); return; } if (N == 2) { printf("- 2 -\n"); return ; } memset(isNotP, 0, sizeof(int) * N); for (i = 3; i <= N; i+=2) { int k = i*i; isNotP[i-1] = 1; while (k <= N) { isNotP[k] = 1; k += i; } } printf("- 2 -\n"); for (i = 3; i <= N; i+=2) if (isNotP[i] == 0) printf("- %d -\n", i); }

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

void printPrime(int n) { bool not_prime = false; for (int i=2; i<n; i++) { not_prime = false; for (int j=2; j<i; j++) { if (i%j==0 && i!=j) { not_prime = true; break; } } if(!not_prime) printf("%d\n", i); } }