在Python中对SPOJ PRIME1的错误答案

Question

我试图通过计算找到的素数来比较我的结果与Wolfram Alpha的结果。

它似乎很好，没有错误。

但是，当我将此解决方案提交给SPOJ时，它显示错误消息“错误答案”。

我也尝试将最终的打印结束=改为“'（空白字符串），但仍然得到了”错误的答案“。

不知道我的筛选算法是否有问题，或输出错误。

**编辑：问题http://www.spoj.pl/problems/PRIME1/

这里是我的PRIME1源代码，链接希望有人能指出我的过错。非常感谢。

希望有人能教我如何编写测试这样的程序，我还在学习，不知道如何做自动化测试的程序，但想学习。

def getPrimeInRange(minNum, maxNum): 
     #just a variation with skipping step of the Sieve of E's 
     processingRange = list(range(minNum, maxNum+1)) 
     #prefix, due to 1 is not a prime 
     if minNum == 1: 
      processingRange[0] = 0 
     sqrtOfMaxNum = int(maxNum ** 0.5) + 1 
     primesUnderSqrt = list(range(sqrtOfMaxNum)) 
     #prefix, due to 1 is not a prime 
     primesUnderSqrt[1] = 0 

     #my strategy is flip all numbers that is not a prime to zero, which equals to False. 
     #for Sieve of E's, all the primes under sqrt of max num are the only needed numbers to sieve primes out. 
     #so here is a smaller Sieve of E's for numbers under sqrt 
     for n in primesUnderSqrt: 
      if n: #which equals to "if n != 0" 
       nowIndex = n + n 
       while True: 
        try: 
         primesUnderSqrt[nowIndex] = 0 
         nowIndex += n 
        except IndexError: 
         break 

     #full aspect sieve 
     for n in primesUnderSqrt: 
      if n: 
       #for easier flip processing, I need the offset number for the flipping. 
       nMultipleMostCloseToMin = n * (minNum // n) 
       if nMultipleMostCloseToMin == minNum: 
        nowIndex = 0 
       elif sqrtOfMaxNum <= minNum: 
        nowIndex = nMultipleMostCloseToMin + n - minNum 
       elif sqrtOfMaxNum > minNum: 
        nowIndex = nMultipleMostCloseToMin + n - minNum + n 

       #happy flippin' 
       while True: 
        try: 
         processingRange[nowIndex] = 0 
         nowIndex += n 
        except IndexError: 
         break 

     return processingRange 

    def main(): 
     todoTimes = int(input()) 
     todoNums = list(range(todoTimes)) 
     stringOutput = '' 
     for i in range(todoTimes): 
      todoNums[i] = input().split() 
      todoNums[i][0] = int(todoNums[i][0]) 
      todoNums[i][1] = int(todoNums[i][1]) 
     for [minNum, maxNum] in todoNums: 
      #countedNum = 0 #for algo debugging 
      for n in getPrimeInRange(minNum, maxNum): 
       if n: 
        stringOutput += str(n) 
        #countedNum += 1 #for algo debugging 
        stringOutput += '\n' 
      stringOutput += '\n' 
      #stringOutput += str(countedNum) #for algo debugging 
     stringOutput = stringOutput.rstrip('\n') 
     print(stringOutput) 


    ifMainSucceed = main() 

Answer 1

你的逻辑的这一部分

if nMultipleMostCloseToMin == minNum: 
    nowIndex = 0 
elif sqrtOfMaxNum <= minNum: 
    nowIndex = nMultipleMostCloseToMin + n - minNum 
elif sqrtOfMaxNum > minNum: 
    nowIndex = nMultipleMostCloseToMin + n - minNum + n 

是错误的。您的elif-条件在这里没有多大意义。如果n不是minNum的除数，n不小于minNum的最小倍数是nMultipleMostCloseToMin + n，不管sqrtOfMaxNum是否大于minNum。你在这里打算的条件是n <= minNum，以避免与素数本身交叉。