Yahoo Interview Question: Write an algorithm that ident... | Glassdoor

Interview Question

Intern Interview(Student Candidate)

Write an algorithm that identifies a prime number from a

  list of numbers ranging 0-100.

Interview Answer

2 Answers


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 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);


Dan on Jul 15, 2013

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, Sign In or Sign Up.