發表新討論
#19425: 請問此題用python通過的高手們


yaushu0306@gmail.com (Yaoshu)

a121. 質數又來囉 | From: [163.24.13.126] | 發表日期: 2019-09-30 08:13 
iAns=0
    for k in range(iStart,iEnd+1):
        if k==1:
            iAns=0
        elif k==2:
            iAns+=1
            continue
        else:
            if k%2==0:
                continue
            else:
                iPrime=0
                iEnd=int(math.sqrt(k))+1
                for i in range(2,iEnd+1):
                    if k % i == 0:
                        iPrime=0
                        break
                    else:
                        iPrime=1
                if iPrime==1:
                    iAns+=1
以上是我的想法，當然是TLE，請問大家問題是否出在雙層迴圈，

我有爬討論看到建立質數表，是否就能加快速度，希望高手們撥冗解惑，感謝

#19429: Re:請問此題用python通過的高手們


asnewchien@gmail.com (david)

a121. 質數又來囉 | From: [61.223.60.73] | 發表日期: 2019-09-30 10:23 
 

建了質數表後，能不能加快速度，自己寫一次才能體會。

#19433: Re:請問此題用python通過的高手們


yaushu0306@gmail.com (Yaoshu)

a121. 質數又來囉 | From: [163.24.13.126] | 發表日期: 2019-09-30 13:51 
 

建了質數表後，能不能加快速度，自己寫一次才能體會。

謝謝你


#20478: Re:請問此題用python通過的高手們


Chengxuan (WeedForJustice)

a121. 質數又來囉 | From: [36.233.242.2] | 發表日期: 2020-01-29 13:03 
iAns=0
    for k in range(iStart,iEnd+1):
        if k==1:
            iAns=0
        elif k==2:
            iAns+=1
            continue
        else:
            if k%2==0:
                continue
            else:
                iPrime=0
                iEnd=int(math.sqrt(k))+1
                for i in range(2,iEnd+1):
                    if k % i == 0:
                        iPrime=0
                        break
                    else:
                        iPrime=1
                if iPrime==1:
                    iAns+=1
以上是我的想法，當然是TLE，請問大家問題是否出在雙層迴圈，

我有爬討論看到建立質數表，是否就能加快速度，希望高手們撥冗解惑，感謝

https://pastebin.com/AtaNXiyU


這是我的想法，但是WA（line 1），看看能不能互相幫忙？

#20483: Re:請問此題用python通過的高手們


wanttogo0718@gmail.com (Hello World)

a121. 質數又來囉 | From: [42.75.141.223] | 發表日期: 2020-01-29 22:13 
iAns=0
    for k in range(iStart,iEnd+1):
        if k==1:
            iAns=0
        elif k==2:
            iAns+=1
            continue
        else:
            if k%2==0:
                continue
            else:
                iPrime=0
                iEnd=int(math.sqrt(k))+1
                for i in range(2,iEnd+1):
                    if k % i == 0:
                        iPrime=0
                        break
                    else:
                        iPrime=1
                if iPrime==1:
                    iAns+=1
以上是我的想法，當然是TLE，請問大家問題是否出在雙層迴圈，

我有爬討論看到建立質數表，是否就能加快速度，希望高手們撥冗解惑，感謝

https://pastebin.com/AtaNXiyU


這是我的想法，但是WA（line 1），看看能不能互相幫忙？

import sys
from math import sqrt
from timeit import timeit

for s in sys.stdin:
    a, b = map(int, s.split(' '))
    if a <= 2: prime_count = 3
    elif a <= 3: prime_count = 2
    elif a <= 5: prime_count = 1
    else: prime_count = 0
    for n in range([a, a+1][a%2==0], b+1, 2):
        if n%3 and n%5:
            ctrl = False
            for i in range(7, int(sqrt(n))+1):
                if n%i == 0:
                    ctrl = True
                    break
            if ctrl == False: prime_count += 1
    print(prime_count)

 

from sys import stdin
from math import sqrt

for s in stdin:
    a, b = map(int, s.split(' '))
    prime_count = 0
    if a == 1: a = 2
    for n in range(a, b+1):
        is_prime = True
        for i in range(2, int(sqrt(n)) + 1):
            if n % i == 0:
                is_prime = False
                break
        prime_count += 1 if is_prime else 0
    print(prime_count)

我有試過建質數表跟直接判斷兩種方式，不過都PLE

Python寫這種題目感覺比較吃虧XD

 

ZeroJudge Forum