#21233: 為什麼總是超時呢?
a121. 質數又來囉
| From: [110.30.103.3] |
發表日期
:
2020-05-04 23:09
import sys
import math
for inputValue in sys.stdin:
startNumber, endNumber = inputValue.split()
result = []
for i in range(int(startNumber), int(endNumber)+1):
sqrtValue = int(math.sqrt(i))
isPrime = True
for j in range(2, sqrtValue+1):
if i % j == 0:
isPrime = False
break
if isPrime:
result.append(i)
print(str(len(result)))
請問各位大大 為什麼這段程式碼總是超時呢?
#21234: Re:為什麼總是超時呢?
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
a121. 質數又來囉
| From: [1.168.26.9] |
發表日期
:
2020-05-04 23:31
你這樣遇到大一點的數字，肯定超時的，
你有沒有發現你的 a010 也比別人慢很多，
去找幾種質數判定法來練習看看。
加油 ^_^
#21238: Re:為什麼總是超時呢?
a121. 質數又來囉
| From: [140.131.116.45] |
發表日期
:
2020-05-05 11:41
你這樣遇到大一點的數字，肯定超時的，你有沒有發現你的 a010 也比別人慢很多，去找幾種質數判定法來練習看看。加油 ^_^
import sys
import math
import time
for inputValue in sys.stdin:
tStart = time.time() # 計時開始
startNumber, endNumber = inputValue.split()
result = []
for i in range(int(startNumber), int(endNumber)+1):
isPrime = True
for j in range(2, int(math.sqrt(i))):
# print(str(i) + '-'+str(j)+','+str(i % j))
if i % j == 0:
isPrime = False
break
if isPrime:
result.append(i)
# print(' '.join([str(r) for r in result]))
tEnd = time.time() # 計時結束
print("It cost %f sec" % (tEnd - tStart)) # 會自動做近位
print(str(len(result)))
後來我 加上時間來看到底花了多少時間
99999000 100000000
It cost 0.116392 sec
52
這題目說
輸入兩個正整數a,b(1<=a<=b<=100000000)。
保證b-a<=1000
我已經取最大了，只要不到0.2秒
這樣應該不至於會超時吧?
還是請問我哪邊誤會了呢?
#21240: Re:為什麼總是超時呢?
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
#21241: Re:為什麼總是超時呢?
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
a121. 質數又來囉
| From: [36.233.33.181] |
發表日期
:
2020-05-05 14:43
還有你寫的 for j in range(2, int(math.sqrt(i)))
如果能略過偶數，時間也可省掉不少。
#21242: Re:為什麼總是超時呢?
#21243: Re:為什麼總是超時呢?
a121. 質數又來囉
| From: [140.131.116.45] |
發表日期
:
2020-05-05 16:34
還有你寫的 for j in range(2, int(math.sqrt(i)))
如果能略過偶數，時間也可省掉不少。
import sys
import math
import time
for inputValue in sys.stdin:
tStart = time.time() # 計時開始
startNumber, endNumber = inputValue.split()
result = []
for i in range(int(startNumber), int(endNumber)+1):
isPrime = True
if i % 2 == 0:
continue
if i % 3 == 0:
continue
if i % 5 == 0:
continue
if i % 7 == 0:
continue
if i % 11 == 0:
continue
for j in range(2, int(math.sqrt(i))):
# print(str(i) + '-'+str(j)+','+str(i % j))
if i % j == 0:
isPrime = False
break
if isPrime:
result.append(i)
# print(' '.join([str(r) for r in result]))
tEnd = time.time() # 計時結束
print("It cost %f sec" % (tEnd - tStart)) # 會自動做近位
print(str(len(result)))
我擋掉了2、3；5、7、11 還是不能ˊˋ
#21266: Re:為什麼總是超時呢?
kobe60116@gmail.com
(xlonely_cat 孤貓)
學校
:
臺北市立龍門國民中學
編號 : 93064
來源 : [203.204.33.87]
最後登入時間 ：
2021-05-30 11:31:37
a121. 質數又來囉
| From: [203.204.33.87] |
發表日期
:
2020-05-10 11:41
還有你寫的 for j in range(2, int(math.sqrt(i)))
如果能略過偶數，時間也可省掉不少。
import sysimport mathimport time
for inputValue in sys.stdin:tStart = time.time() # 計時開始startNumber, endNumber = inputValue.split()
result = []for i in range(int(startNumber), int(endNumber)+1):isPrime = Trueif i % 2 == 0:continueif i % 3 == 0:continueif i % 5 == 0:continueif i % 7 == 0:continueif i % 11 == 0:continue
for j in range(2, int(math.sqrt(i))):# print(str(i) + '-'+str(j)+','+str(i % j))if i % j == 0:isPrime = Falsebreakif isPrime:result.append(i)# print(' '.join([str(r) for r in result]))tEnd = time.time() # 計時結束print("It cost %f sec" % (tEnd - tStart)) # 會自動做近位print(str(len(result)))
我擋掉了2、3；5、7、11 還是不能ˊˋ
2%2=0 2是質數阿\
2,3,5,7,11 也都被你擋掉了
ZeroJudge Forum