Hi everybody!
I've just started solving some problems, and after solving PRIME1 in C I thought doing it in Python would be a good idea, since I don't know Python at all
. Although the algorithm is ok (I guess, I got AC in C and this is mostly a port of that algorithm), I get NZEC when I submit it to the Judge.
Here's the code:
def getOffset(num, lowerBound):
return num - lowerBound
def getNumber(offset, lowerBound):
return offset + lowerBound
def getLowestMultiple(num, lowerBound):
result = lowerBound % num
if ((result == lowerBound) and (num > lowerBound)):
result = num + num
else:
result += lowerBound + (num - (lowerBound % num))
return result
def getPrimes(lowerBound, upperBound):
primes = [];
if ((lowerBound == 2) or (lowerBound == 1 and upperBound >= 2)):
print "2";
lowerBound = 3;
for i in range(lowerBound, upperBound + 1):
primes.append(i % 2)
check = math.trunc(math.sqrt(upperBound)) + 1
for i in range(3, check, 2):
if ((i >= lowerBound) and (not primes[getOffset(i, lowerBound)])):
continue
j = getLowestMultiple(i, lowerBound)
while (j <= upperBound):
primes[getOffset(j, lowerBound)] = 0;
j += i
for i in range(lowerBound, upperBound + 1):
if (primes[getOffset(i, lowerBound)] == 1):
print i;
def getInputs():
runs = int(sys.stdin.readline())
inputs = []
while (runs > 0):
runs -= 1
input = sys.stdin.readline()
input = input.split(" ", 2)
#inputs.append([map(int, x) for x in input])
inputs.append([int(input[0]), int(input[1])])
return inputs
inputs = getInputs()
for pair in inputs:
getPrimes(pair[0], pair[1])
print ""
The answers are fine. Also, I think the execution time fits in the 6 sec time limit. I don't really know what the problem is. I also tried processing the inputs one by one (get a pair, find the primes, get the next pair etc.) and I get the same answer.
Help? 