#22558: 建表 or 不建表？

snakeneedy (蛇~Snake)

學校 : 國立高雄師範大學附屬高級中學
編號 : 7661
來源 : [114.40.8.251]
最後登入時間：
2023-01-25 19:16:06

a121. 質數又來囉 | From: [218.161.41.139] | 發表日期 : 2020-09-15 13:30

最近幾次 AC 中，用建表的為 (39ms, 280KB)，不建表的為 (79ms, 148KB)，
「看起來」是建表比不建表用了大略兩倍的空間，來節省一半的時間，但並不代表哪種比較好。

接下來分別說明自己建表和不建表的方法

先講「不建表」

大致就是遵循質數的判定規則，對某數 N，依序拿整數 2 ~ sqrt(N) 來除 N，能整除表示合數，都不整除則為質數。

稍微做了最佳化，將質數用 6 歸納，除了 2, 3, 5 之外，(6k), (6k+2), (6k+4) 必能被 2 整除，而 (6k+3) 必能被 3 整除，所以其他質數必定能寫成 (6n+1) 或 (6n+5)
（但 (6n+1), (6n+5) 的數不一定就是質數，如 25=6x4+1=5x5）

用上述規則，再判斷 N 是否為質數時，只要找 2, 3, 5, 7(=6x1+1), 11(=6x1+5), ... 來判斷即可

再講「建表」

由於題目給最大正整數為 100000000，代表只要找到 1~10000 之間的質數即可

先用上述「不建表」的邏輯，對 1~10000 的數判定是否為質數，並存到一個陣列裡，這邊我是使用 std::vector，表建好之好，再就題目給的數，從剛剛建好的表中，找出質數來判定即可

稍微做了最佳化，1~10000 的數判斷完，開了另一個陣列 isPrime[10001]，儲存該數是為質數，之後只要遇到 1~10000 的數，只要查 isPrime[N] 就好，不用再做是否整除的判斷

若還有做得不夠好，就是我要繼續學的部分了

| 回應文章 | 回原始文章

#25770: Re:建表 or 不建表？

asd21569093@gmail.com (YuDe Kuan)

學校 : 不指定學校
編號 : 155055
來源 : [118.161.138.202]
最後登入時間：
2024-01-26 10:48:31

a121. 質數又來囉 | From: [118.161.188.248] | 發表日期 : 2021-06-21 15:25

最近幾次 AC 中，用建表的為 (39ms, 280KB)，不建表的為 (79ms, 148KB)，
「看起來」是建表比不建表用了大略兩倍的空間，來節省一半的時間，但並不代表哪種比較好。

接下來分別說明自己建表和不建表的方法

先講「不建表」

大致就是遵循質數的判定規則，對某數 N，依序拿整數 2 ~ sqrt(N) 來除 N，能整除表示合數，都不整除則為質數。

稍微做了最佳化，將質數用 6 歸納，除了 2, 3, 5 之外，(6k), (6k+2), (6k+4) 必能被 2 整除，而 (6k+3) 必能被 3 整除，所以其他質數必定能寫成 (6n+1) 或 (6n+5)
（但 (6n+1), (6n+5) 的數不一定就是質數，如 25=6x4+1=5x5）

用上述規則，再判斷 N 是否為質數時，只要找 2, 3, 5, 7(=6x1+1), 11(=6x1+5), ... 來判斷即可

再講「建表」

由於題目給最大正整數為 100000000，代表只要找到 1~10000 之間的質數即可

先用上述「不建表」的邏輯，對 1~10000 的數判定是否為質數，並存到一個陣列裡，這邊我是使用 std::vector，表建好之好，再就題目給的數，從剛剛建好的表中，找出質數來判定即可

稍微做了最佳化，1~10000 的數判斷完，開了另一個陣列 isPrime[10001]，儲存該數是為質數，之後只要遇到 1~10000 的數，只要查 isPrime[N] 就好，不用再做是否整除的判斷

若還有做得不夠好，就是我要繼續學的部分了

照你的不建表寫一直TLE(9)，可以幫我看看嗎

def p(number):
    ab=int(number**(1/2))+1
    for i in range(2,ab):
        if number%i==0:
            return False
    return True
while True:
    try:
        sum=0
        xin=[]
        a,b=map(int,input().split())
        for io in range(a,b+1):
            if io%6==1 or io%6==5 or io==5 or io==2 or io==3:
                xin.append(io)
        for q in xin:
            if p(q):
                sum+=1
        print(sum)
    except EOFError:
        break
 