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

SunGard

Acquired by FIS

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)

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