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.

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