If you change the upper_bound to upper_bound = int(math.sqrt(1000000000)) + 123456, then it will pass all the test cases.
Now, can you figure why so? I'll leave it as an exercise to you.
题
I am getting Wrong Answer with the following code in python for SPOJ's PRIME1 problem at http://www.spoj.com/problems/PRIME1/. I have tested it on various testcases myself, but cannot find a failing testcase. Can someone please spot the problem in my code?
This code produces nothing for testcases that don't give any prime as output. First i pre-compute primes upto sqrt(1 billion) and then if the requested range has high value less than sqrt(1 billion), i simply print the primes from the pre-computed array, else i run sieve() with usePrimes = True, which uses the pre-computed primes to rule out the non-primes in the given range.
Thanks.
import math
from bisect import bisect_left
from bisect import bisect_right
primes = []
upper_bound = int(math.sqrt(1000000000)) + 1
usePrimes = False
printNL = False
T = 0
def sieve(lo, hi):
global usePrimes, primes, printNL
atleast_one = False
arr = range(lo,hi+1)
if usePrimes:
for p in primes:
if p*p > hi:
break
less = int(lo/p) * p
if less < lo:
less += p
while less <= hi:
arr[less - lo] = 0
less += p
for num in arr:
if num != 0:
atleast_one = True
if printNL:
print ''
printNL = False
print num
else:
atleast_one = True
for k in xrange(2,hi):
if k*k > hi:
break
if arr[k] == 0:
continue
less = k + k
while less <= hi:
arr[less] = 0
less += k
for num in arr:
if num > 1:
primes.append(num)
return atleast_one
def printPrimesInRange(lo,hi):
global primes, printNL
atleast_one = False
if hi < upper_bound:
for p in primes[bisect_left(primes,lo):bisect_right(primes,hi)]:
atleast_one = True
if printNL:
print ''
printNL = False
print p
else:
atleast_one = sieve(lo,hi)
return atleast_one
sieve(0, upper_bound)
usePrimes = True
T = input()
while T > 0:
lo, hi = [eval(y) for y in raw_input().split(' ')]
atleastOne = printPrimesInRange(lo,hi)
if atleastOne:
printNL = True
T -= 1
解决方案
If you change the upper_bound to upper_bound = int(math.sqrt(1000000000)) + 123456, then it will pass all the test cases.
Now, can you figure why so? I'll leave it as an exercise to you.