SumoLogic Interview Question
Software Engineer in TestsCountry: India
Interview Type: Phone Interview
I checked around online and the first answer I gave is actually finding prime numbers using trial division. Here is a verified sieve of eratosthnese algorithm in python:
def primes_sieve2(limit):
a = [True] * limit # Initialize the primality list
a[0] = a[1] = False
for (i, isprime) in enumerate(a):
if isprime:
yield i
for n in xrange(i*i, limit, i): # Mark factors non-prime
a[n] = False
void findPrime(unsigned long n, vector<long>& result)
{
if (n <= 3) {
result.push_back(2);
result.push_back(3);
} else {
long double j;
result.push_back(2);
result.push_back(3);
for (long i = 4; i <= n; i++) {
long double sqrtI = sqrt(i);
for (j = 2; j <= sqrtI && (i % (long)j); j++);
if (j >= sqrtI && (i % (long)j))
result.push_back(i);
}
}
}
Using Sieve of Eratosthenes algorithm:
1. Create an array container to hold all of the prime numbers you have found.
2. As you start your loop eliminate, 1, 2, 3, and any number divisible by them. When you get to another prime number, like 5, add it to your array of prime numbers.
3. For every number you encounter, if it cannot be divided by any number in your array of primes, it is prime. Add it to your array.
Worst-case running time, I believe is O(n^2).
In python:
- Anonymous August 06, 2014