#22558: 建表 or 不建表?


snakeneedy (蛇~Snake)

School : 國立高雄師範大學附屬高級中學
ID : 7661
IP address : [123.194.188.217]
Last Login :
2021-01-30 06:04:44
a121. 質數又來囉 | From: [218.161.41.139] | Post Date : 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)

School : No School
ID : 155055
IP address : [118.161.189.207]
Last Login :
2021-06-28 13:28:05
a121. 質數又來囉 | From: [118.161.188.248] | Post Date : 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
 
 
#25773: Re:建表 or 不建表?


asnewchien@gmail.com (david)

School : No School
ID : 68108
IP address : [61.223.48.151]
Last Login :
2021-09-16 15:15:00
a121. 質數又來囉 | From: [61.223.48.57] | Post Date : 2021-06-21 16:47

先不談建表或不建表。
 
你的 def p(number):
就有很大的改善空間
for i in range(2,ab)
連偶數都試除了, 能快嗎。
 
當然這樣也是過不了啦。
想想別的方法,
 
#26160: Re:建表 or 不建表?


liu76214@gmail.com (Andrew liu)

School : 新竹市立建功高級中學
ID : 92407
IP address : [111.243.122.123]
Last Login :
2021-08-15 15:26:39
a121. 質數又來囉 | From: [111.243.107.81] | Post Date : 2021-07-20 09:33

先不談建表或不建表。
 
你的 def p(number):
就有很大的改善空間
for i in range(2,ab)
連偶數都試除了, 能快嗎。
 
當然這樣也是過不了啦。
想想別的方法,

跩三小

 
#26161: Re:建表 or 不建表?


asnewchien@gmail.com (david)

School : No School
ID : 68108
IP address : [61.223.48.151]
Last Login :
2021-09-16 15:15:00
a121. 質數又來囉 | From: [125.224.192.62] | Post Date : 2021-07-20 12:52

我上面的回應, 算客氣吧。

 
#26162: Re:建表 or 不建表?


asnewchien@gmail.com (david)

School : No School
ID : 68108
IP address : [61.223.48.151]
Last Login :
2021-09-16 15:15:00
a121. 質數又來囉 | From: [125.224.192.62] | Post Date : 2021-07-20 13:05

我上面的回應, 算客氣吧。

 

cpp 的 user 

即使寫法普通,勉強也能 ac

 

python 就是比較慢,

硬要參考 cpp 的解法,往往就是超時。

非得要絞盡腦汁才能通過,

這也是樂趣之一。

 

上面我只是想請他趕快想其他的方法,

上面的方法,無法 AC

 

 
#26252: Re:建表 or 不建表?


qawl987 (中央地板好滑)

School : No School
ID : 149523
IP address : [1.161.125.69]
Last Login :
2021-09-16 09:53:12
a121. 質數又來囉 | From: [1.161.75.102] | Post Date : 2021-07-27 21:22

先不談建表或不建表。
 
你的 def p(number):
就有很大的改善空間
for i in range(2,ab)
連偶數都試除了, 能快嗎。
 
當然這樣也是過不了啦。
想想別的方法,


是真的看起來很像在跟小朋友講話,很像想要引導式學習,卻看起來只是來邱的

 
ZeroJudge Forum