iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 25
0
Software Development

從0開始學習程式-Python系列 第 26

[Day29] 實例演練:質數表

  • bruteforce 暴力破解法:窮舉所有可能,將該數除以比他小的每個正整數,如果有能被他整除的就不是質數
  • Eratosthenes方法:數字由小到大,確認是質數後,將其所有倍數刪除,最後留下來的必定是質數
    Hint:若為合數,那麼它的最小質因數必定小於等於它的平方根!
def bruteforce(n):
	if n<=2:
		return 0
	else:
		prime=[]
	for i in range(2,n):
		k=0 # 質數標誌,0為質數
		for j in range(2,i):
			if i%j ==0:
				k=1
		if k==0:
			prime.append(i)
	return prime
    
def eratosthenes(n):
	isPrime = [True]*(n+1)
	isPrime[1] = False
	for i in range(2, int(n** 0.5) + 1):# 只需要做到根號n就可以完成了
		if  isPrime[i]: 
            # if isPrime[i] is True, thast is, i is prime value
			for j in range(i*i, n+1, i): # 如果i是質數,則篩掉它的倍數
				isPrime[j] = False
	return [x for x in range(2,n+1) if isPrime[x]]

if __name__ == "__main__":
    print(bruteforce(120))
	print(eratosthenes(120))
#output:[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]

上一篇
[Day28] 實例演練Leetcode239
下一篇
[Day30] 腫麼讀由你
系列文
從0開始學習程式-Python32

尚未有邦友留言

立即登入留言