iT邦幫忙

2021 iThome 鐵人賽

DAY 27
0
自我挑戰組

一個月的演算法挑戰系列 第 27

Day27:質數判定法(Primality Test)

質數(Prime number)

在國中時有學過質數,質數除了1和本身之外,沒有其他因數的大於1的自然數。質數的應用很廣泛,前幾天所提到的公開金鑰加密演算法,RSA及Diffie–Hellman Key Exchange就是以質數作為基礎。

對於質數的興趣是起源於「龍紋身的女孩」這一系列的書,裡面就有提到女主角莎蘭德破解國安局加密後的訊息,其中使用質數加密,當時就去找資料,意外發現這東西太有趣了。找資料的過程中,意外了解「自然界中的質數-週期蟬」。

週期蟬

Wiki中有提到「週期蟬」又被稱為十七年蟬或十三年蟬,其生命週期為17年或13年,一生絕大多數時間在地下度過,靠吸食樹根的汁液生存。在地下生活十三年或十七年後,同種蟬的若蟲同時破土而出,在4-6周內羽化、交配、產卵、死亡,而卵孵化後進入下一個生命周期。因此某一年份在美國東部一些地方每過十七或十三年就會突然出現的大量的蟬,成為一種奇景。

科學家普遍認為的原因是,首先這兩個周期都很長,因為周期蟬出現於距今180萬年前,那時北美氣溫低,有時會遇到冷夏,成年蟬需要高溫,因此長生命周期可以提高成活率。其次這兩個周期都是質數,這樣可以避開其他種類的掠食者。如果不是質數,那麼就有更多機會和自己天敵的生命周期相重疊,降低族群數量。

這裡有另一篇延伸的週期蟬計算方式:
Evolution of periodicity in periodical cicadas


質數判定法(Primality Test)

質數判定法(Primality Test),是檢定一個給定的整數是否為質數的測試。

用Python實現:

def is_prime(number):
    for i in range(2,number):
        if number % i == 0:
            return False
    return True

n = int(input('輸入一個正整數:'))

if is_prime(n):
    print('是質數')
else:
    print('不是質數')

用JavaScript實現:

function isPrime(num) {
    let t = parseInt(Math.sqrt(num));
    for (let i = 2; i < t; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

上一篇
Day26:河內塔(Tower of Hanoi)
下一篇
Day28:網頁排名演算法(PageRank)
系列文
一個月的演算法挑戰30

尚未有邦友留言

立即登入留言