SunGard Interview Question: Write a program to find prim... | Glassdoor

Interview Question

Senior Software Engineer Interview Pune (India)

Write a program to find prime numbers between 1 to

  100000. primes = [] for x in range(1,100000): for y in range (2, x-1): if x % y == 0: break else: primes.append(x) print "Prime Numbers: ", primes NOW OPTIMIZE IT. (Yeilling)
Answer

Interview Answer

4 Answers

0

THE RANGE OF Y SHOULD BE (2, X/2) INSTEAD OF (2, X-1) FOR OPTIMIZED CODE

Anonymous on Sep 3, 2014
0

time ./isprime2.8s:

#!/usr/bin/python

def isPrime(n):
    if n == 2 or n == 3:
        return 1

    if n % 2 == 0 or n % 3 == 0:
        return 0

    i = 5
    w = 2
    while i*i <= n:
        if n % i == 0:
            return 0

        i += w
        w = 6 - w

    return 1

primes = []

for i in range(1, 1000000):
    if isPrime(i):
        primes.append(i)

print primes

Scott Gillespie on Feb 4, 2017
0

in C,
#include

int isPrime(int);

int main() {

    const int MAX = 1000000;

    int *primes = malloc(MAX*sizeof(int));

    int i;
    for (i=0; i<MAX; i++) {
        if (isPrime(i)) {
            primes[i] = i;
            printf(" %d ", primes[i]);
        }
    }
}

int isPrime(int n) {
    int i = 5;
    int w = 2;

    if ((n == 2) || (n == 3)) {
        return 1;
    }

    if ((n % 2 == 0) || (n % 3 == 0)) {
        return 0;
    }

    while ((i * i) <= n) {
        if (n % i == 0) {
            return 0;
        }
        i += w;
        w = 6 - w;
    }

    return 1;
}

Scott Gillespie on Feb 4, 2017
0

C code took less than 1 second.
Python code took about 2.8s with optimization.
Your code took 1 minute and 43 seconds. That's why they were yelling, I guess? Man, they should really learn to relax if they're yelling during the interview process at potential candidates! :)

Scott Gillepie on Feb 4, 2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.