成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

PHP算法之判斷是否是質(zhì)數(shù)

Eidesen / 511人閱讀

摘要：質(zhì)數(shù)的定義質(zhì)數(shù)又稱素?cái)?shù)。一個(gè)大于的自然數(shù)，除了和它自身外，不能整除其他自然數(shù)的數(shù)叫做質(zhì)數(shù)否則稱為合數(shù)。實(shí)現(xiàn)思路循環(huán)所有可能的備選數(shù)字，然后和中間數(shù)以下且大于等于的整數(shù)進(jìn)行整除比較，如果能夠被整數(shù)，則肯定不是質(zhì)數(shù)，相反，就是質(zhì)數(shù)。

質(zhì)數(shù)的定義 
質(zhì)數(shù)又稱素?cái)?shù)。一個(gè)大于1的自然數(shù)，除了1和它自身外，不能整除其他自然數(shù)的數(shù)叫做質(zhì)數(shù)；否則稱為合數(shù)。
實(shí)現(xiàn)思路

循環(huán)所有可能的備選數(shù)字，然后和中間數(shù)以下且大于等于2的整數(shù)進(jìn)行整除比較，如果能夠被整數(shù)，則肯定不是質(zhì)數(shù)，相反，就是質(zhì)數(shù)。

第一種算法

這也是最可能先想到的，也就是直接和備選數(shù)的中間數(shù)去比較，算法源碼如下：

/**
 * 獲取所有的質(zhì)數(shù)
 * @param array $arr
 * @return array
 */
function get_prime_number($arr = []) {
    // 質(zhì)數(shù)數(shù)組
    $primeArr = [];
    // 循環(huán)所有備選數(shù)
    foreach ($arr as $value) {
        // 備選數(shù)和備選數(shù)的中間數(shù)以下的數(shù)字整除比較
        for ($i = 2; $i <= floor($value / 2); $i++) {
            // 能夠整除，則不是質(zhì)數(shù)，退出循環(huán)
            if ($value % $i == 0) {
                break;
            }
        }
        // 被除數(shù)$j比備選數(shù)的中間數(shù)大的則為質(zhì)數(shù)
        // 這樣判斷的依據(jù)：
        // 假如備選數(shù)為質(zhì)數(shù)，則內(nèi)層的for循環(huán)不會(huì)break退出，則執(zhí)行完畢，$i會(huì)繼續(xù)+1，即最后$i = floor($value / 2) + 1
        // 假如備選數(shù)不為質(zhì)數(shù)，則內(nèi)層的for循環(huán)遇到整除就會(huì)break退出，$i不會(huì)繼續(xù)+1，即最后$i <= floor($value / 2)
        if ($value != 1 && $i > floor($value / 2)) {
            $primeArr[] = $value;
        }
    }
    return $primeArr;
}

### 第二種算法

認(rèn)真的來(lái)說(shuō)的話，這也不算是另外一種算法，只是對(duì)于第一種的稍微點(diǎn)點(diǎn)優(yōu)化，及中間最大數(shù)的優(yōu)化，縮小比較范圍，算法源碼如下：

/**
 * 獲取所有的質(zhì)數(shù)
 * @param array $arr
 * @return array
 */
function get_prime_number($arr = []) {
    // 質(zhì)數(shù)數(shù)組
    $primeArr = [];
    // 循環(huán)所有備選數(shù)
    foreach ($arr as $value) {
        // 備選數(shù)和備選數(shù)的中間數(shù)以下的數(shù)字整除比較
        for ($i = 2; $i <= floor($value / $i); $i++) {
            // 能夠整除，則不是質(zhì)數(shù)，退出循環(huán)
            if ($value % $i == 0) {
                break;
            }
        }
        // 被除數(shù)$j比備選數(shù)的中間數(shù)大的則為質(zhì)數(shù)
        // 這樣判斷的依據(jù)：
        // 假如備選數(shù)為質(zhì)數(shù)，則內(nèi)層的for循環(huán)不會(huì)break退出，則執(zhí)行完畢，$i會(huì)繼續(xù)+1，即最后$i = floor($value / $i) + 1
        // 假如備選數(shù)不為質(zhì)數(shù)，則內(nèi)層的for循環(huán)遇到整除就會(huì)break退出且$i不會(huì)繼續(xù)+1，即最后$i <= floor($value / $i)
        if ($value != 1 && $i > floor($value / $i)) {
            $primeArr[] = $value;
        }
    }
    return $primeArr;
}
第三種算法

這個(gè)的話也是對(duì)于第二種的優(yōu)化，即，直接從完整數(shù)組中刪除所有不是質(zhì)數(shù)的數(shù)即可，算法源碼如下：

/**
 * 獲取所有的質(zhì)數(shù)
 * @param array $arr
 * @return array
 */
function get_prime_number_three($arr = []) {
    // 質(zhì)數(shù)數(shù)組
    $primeArr = $arr;
    // 循環(huán)所有備選數(shù)
    foreach ($primeArr as $key => $value) {
        if ($value == 1) {
            unset($primeArr[$key]);
            continue;
        }
        // 備選數(shù)和備選數(shù)的中間數(shù)以下的數(shù)字整除比較
        for ($i = 2; $i <= floor($value / $i); $i++) {
            // 能夠整除，則不是質(zhì)數(shù)，從數(shù)組中刪除且退出循環(huán)
            if ($value % $i == 0) {
                unset($primeArr[$key]);
                break;
            }
        }
    }
    // 重置數(shù)組索引返回
    return array_values($primeArr);
}
使用方法

比如，求1-100的所有質(zhì)數(shù)

// 所有備選數(shù)數(shù)組
$numberArr = range(1, 100, 1);
// 獲取備選數(shù)中的所有質(zhì)數(shù)
$primeNumberArr = get_prime_number($numberArr);
// 輸出打印
print_r($primeNumberArr);

又比如，求指定數(shù)組中的所有質(zhì)數(shù)

// 所有備選數(shù)數(shù)組
$numberArr = [11, 22, 33, 66, 77, 3, 8, 10, 99];
// 獲取備選數(shù)中的所有質(zhì)數(shù)
$primeNumberArr = get_prime_number($numberArr);
// 輸出打印
print_r($primeNumberArr);
最后

如有說(shuō)的不對(duì)的地方，請(qǐng)大家多多諒解，歡迎留言和我溝通、交流，謝謝！

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/30896.html

相關(guān)文章

  • 加密算法之非對(duì)稱加密

    摘要：算法公鑰加密算法是年由羅納德李維斯特阿迪薩莫爾和倫納德阿德曼一起提出的。是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數(shù)密碼攻擊，已被推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。 上篇文章介紹了對(duì)稱加密的原理，但是它的最大問(wèn)題就是加密和解密的密鑰是相同的，并且不能保證密鑰能安全的送到雙方手里，即使安全的送到雙方手里，免不了內(nèi)部會(huì)有臥底的存在 非對(duì)稱加密 既然有對(duì)稱加密，那么自然會(huì)聯(lián)想到非...

    dongxiawu 評(píng)論0 收藏0

  • 求質(zhì)數(shù)的各個(gè)算法比較

    摘要：首先明確一下概念質(zhì)數(shù)又稱素?cái)?shù)，有無(wú)限個(gè)。質(zhì)數(shù)定義為在大于的自然數(shù)中，除了和它本身以外不再有其他因數(shù)的數(shù)稱為質(zhì)數(shù)。以內(nèi)質(zhì)數(shù)表質(zhì)數(shù)的個(gè)數(shù)是無(wú)窮的。 首先聲明本人水平有限，僅僅做一下記錄，有錯(cuò)的地方請(qǐng)指正，文章垃圾請(qǐng)包容??！ 在網(wǎng)上不小心瀏覽到一篇技術(shù)博客，叫做《求質(zhì)數(shù)算法的N種境界（N>10）》，寫得很好，有興趣的讀者自己去搜索。然后就想自己去試試這篇博客里寫得各種求質(zhì)數(shù)的方法。 不想搭...

    QLQ 評(píng)論0 收藏0

  • 小李飛刀：做題第八彈！

    摘要：認(rèn)真做題的分割線第一題乘積最大子序列難度中等給定一個(gè)整數(shù)數(shù)組，找出一個(gè)序列中乘積最大的連續(xù)子序列該序列至少包含一個(gè)數(shù)。 寫在前面的話 慢慢轉(zhuǎn)變思路，不再死磕不會(huì)做的題，思路可以先借鑒，但是一定要吃透透。上周末看完看完了《算法圖解》，感覺對(duì)一些題目的思路有比較大的幫助，但是還是要在實(shí)踐中理解。 認(rèn)真做題的分割線 第一題 152. 乘積最大子序列難度：中等給定一個(gè)整數(shù)數(shù)組nums，找出一個(gè)...

    ztyzz 評(píng)論0 收藏0

  • 算法之不定期更新（一）（2018-04-12）

    摘要：算法的確有他獨(dú)特的魅力。然后我在做這個(gè)題的時(shí)候，其實(shí)也用到了類似質(zhì)因數(shù)分解，只是其實(shí)我們可以更好的利用到因數(shù)這一個(gè)特性。判斷一個(gè)數(shù)是否是質(zhì)數(shù)質(zhì)數(shù)列表一開始我們認(rèn)為每一個(gè)數(shù)都可能是自身的冪線性篩為質(zhì)數(shù)遍歷質(zhì)數(shù)列表為質(zhì)數(shù)的冪 前言 從三月份到現(xiàn)在，大大小小筆試了十幾家公司（主要是因?yàn)橐恢眘olo code，沒(méi)人內(nèi)推），然后也能感覺到自己的進(jìn)步把。從編程題只能ac一題到后來(lái)的ak。今天面騰訊...

    Martin91 評(píng)論0 收藏0

  • RSA加密算法中的數(shù)學(xué)

    摘要：背景不對(duì)稱加密算法可是算是世界上最重要的加密算法，其中包括我們熟悉的的加密。現(xiàn)在我們分步來(lái)看，這個(gè)全球最重要的加密算法，都需要哪些數(shù)學(xué)知識(shí)。我們常說(shuō)的算法中的多少位，就是用二進(jìn)制表示后的位數(shù)，在我們例子就是位。其中表示兩個(gè)數(shù)的最大公約數(shù)。 背景 RSA不對(duì)稱加密算法可是算是世界上最重要的加密算法，其中包括我們熟悉的https的加密。為了完全弄明白他的實(shí)現(xiàn)原理，我們需要對(duì)數(shù)論這門學(xué)科，有...

    ?xiaoxiao, 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<