PHP算法之判斷是否是質數

Eidesen 發布于2019-07-01 12:31 / 508人閱讀

摘要：質數的定義質數又稱素數。一個大于的自然數，除了和它自身外，不能整除其他自然數的數叫做質數否則稱為合數。實現思路循環所有可能的備選數字，然后和中間數以下且大于等于的整數進行整除比較，如果能夠被整數，則肯定不是質數，相反，就是質數。

質數的定義

質數又稱素數。一個大于1的自然數，除了1和它自身外，不能整除其他自然數的數叫做質數；否則稱為合數。

實現思路

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

第一種算法

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

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

### 第二種算法

認真的來說的話，這也不算是另外一種算法，只是對于第一種的稍微點點優化，及中間最大數的優化，縮小比較范圍，算法源碼如下：

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

第三種算法

這個的話也是對于第二種的優化，即，直接從完整數組中刪除所有不是質數的數即可，算法源碼如下：

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

使用方法

比如，求1-100的所有質數

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

又比如，求指定數組中的所有質數

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

最后

如有說的不對的地方，請大家多多諒解，歡迎留言和我溝通、交流，謝謝！

云服務器 GPU云服務器 java判斷是否質數 php判斷是否是整型 js判斷是否是域名 js 判斷是否是集合

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/30896.html

加密算法之非對稱加密

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

dongxiawu 2019-06-27 15:36 評論0 收藏0
求質數的各個算法比較

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

QLQ 2019-06-27 16:17 評論0 收藏0
小李飛刀：做題第八彈！

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

ztyzz 2019-07-31 10:11 評論0 收藏0
算法之不定期更新（一）（2018-04-12）

摘要：算法的確有他獨特的魅力。然后我在做這個題的時候，其實也用到了類似質因數分解，只是其實我們可以更好的利用到因數這一個特性。判斷一個數是否是質數質數列表一開始我們認為每一個數都可能是自身的冪線性篩為質數遍歷質數列表為質數的冪前言從三月份到現在，大大小小筆試了十幾家公司（主要是因為一直solo code，沒人內推），然后也能感覺到自己的進步把。從編程題只能ac一題到后來的ak。今天面騰訊...

Martin91 2019-08-22 16:16 評論0 收藏0
RSA加密算法中的數學

摘要：背景不對稱加密算法可是算是世界上最重要的加密算法，其中包括我們熟悉的的加密?，F在我們分步來看，這個全球最重要的加密算法，都需要哪些數學知識。我們常說的算法中的多少位，就是用二進制表示后的位數，在我們例子就是位。其中表示兩個數的最大公約數。背景 RSA不對稱加密算法可是算是世界上最重要的加密算法，其中包括我們熟悉的https的加密。為了完全弄明白他的實現原理，我們需要對數論這門學科，有...

?xiaoxiao, 2019-08-21 17:53 評論0 收藏0