首頁猿問為什么我們檢查一個(gè)素?cái)?shù)的平方根來確...

為什么我們檢查一個(gè)素?cái)?shù)的平方根來確定它是否是素?cái)?shù)？

算法

搖曳的薔薇 2019-06-25 16:13:36

為什么我們檢查一個(gè)素?cái)?shù)的平方根來確定它是否是素?cái)?shù)？要檢驗(yàn)一個(gè)數(shù)字是否素?cái)?shù)，為什么我們要測(cè)試它是否只能被除以到這個(gè)數(shù)的平方根呢？

查看完整描述

3 回答

料青山看我應(yīng)如是

TA貢獻(xiàn)1772條經(jīng)驗(yàn) 獲得超8個(gè)贊

如果一個(gè)數(shù)字n不是質(zhì)數(shù)，它可以被分解為兩個(gè)因素。a和b:

n = a * b

如果兩者都是a和b的平方根大于n，然后a * b會(huì)比n..因此，這些因子中至少有一個(gè)必須小于或等于n，如果我們找不到任何小于或等于平方根的因素，n一定是一流的。

反對(duì) 回復(fù) 2019-06-25

達(dá)令說

TA貢獻(xiàn)1821條經(jīng)驗(yàn) 獲得超6個(gè)贊

一個(gè)更直觀的解釋是：-

100的平方根是10，假設(shè)a，b=100，對(duì)于不同對(duì)的a和b。

如果a=b，那么它們是相等的，并且是100的平方根。也就是10。

如果其中一個(gè)小于10，另一個(gè)必須更大。例如，5x20=100。一個(gè)大于10，另一個(gè)小于10。

考慮到x，b，如果其中一個(gè)下降，另一個(gè)必須變得更大來補(bǔ)償，所以產(chǎn)品保持在100。它們圍繞平方根旋轉(zhuǎn)。

101的平方根約為10.049875621。所以，如果你測(cè)試數(shù)字101的素?cái)?shù)，你只需要試著整到10，包括10。但是8，9和10本身并不是素?cái)?shù)，所以你只需要測(cè)試到7，這是素?cái)?shù)。

因?yàn)槿绻幸粚?duì)因子，其中一個(gè)大于10，另一個(gè)必須小于10，如果不存在較小的一個(gè)，就沒有匹配的更大的因子101。

如果你測(cè)試121，平方根是11。你必須測(cè)試素整數(shù)1到11(包括在內(nèi))，看看它是否均勻。11次11次，所以121不是素?cái)?shù)。如果你在10點(diǎn)停止，而不是11次測(cè)試，你就會(huì)錯(cuò)過11次。

假設(shè)只測(cè)試奇數(shù)，則必須測(cè)試大于2但小于或等于平方根的每一個(gè)素?cái)?shù)。

反對(duì) 回復(fù) 2019-06-25

關(guān)注

舉報(bào)

0/150

提交

取消

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)