Interview Question

Intern Interview(Student Candidate)

Write an algorithm that identifies a prime number from a

  list of numbers ranging 0-100.
Answer

Interview Answer

2 Answers

0

You could do this fairly efficiently using a trivial implementation of the sieve of eratosthenes. The initial setup cost of the sieve is O(n log log n), but once generated the amortised time to identify whether or not a number between 0 .. n is prime ends up being O(1) as n approaches infinity:

function next_prime(i, sieve) {
    for (; i < sieve.length; i++) {
        if (sieve[i] == 0) {
            break;
        }
    }
    return i;
};

function build_sieve(n) {
    var sieve = [];
    var prime = 1;
    var sum = 0;
    while (prime <= n) {
        prime = next_prime(prime + 1, sieve);
        sum = prime;
        while (sum <= n) {
            sum = sum + prime;
            sieve[sum] = 1;
        }
    }
    return sieve;
};

function identify_prime(n) {
    if (n < 0 || n > 100) {
        throw new Error(n + ' is outside accepted range');
    }
    return sieve[n] === undefined;
};

function test_prime(n) {
    if (identify_prime(n)) {
        console.log(n + ' is prime');
    } else {
        console.log(n + ' is not prime');
    }
};

var sieve = build_sieve(100);

test_prime(3);
test_prime(88);
test_prime(17);
test_prime(100);

Dan on Jul 15, 2013
0

I feel this is a trick question. Since we know the range and it is such a small range, the quickest algorithm would be:

is_prime = (num)->
  return num in [2, 3, 5, 7, 11, 13, 17, 19, 23...]

Mihir Sathe on Aug 18, 2013

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up