素?cái)?shù)的定義

素?cái)?shù)是指大于1的自然數(shù)，除了1和它本身外，沒(méi)有其他正因數(shù)。換句話說(shuō)，素?cái)?shù)只能被1和它自身整除。

素?cái)?shù)的例子

常見(jiàn)的素?cái)?shù)包括2、3、5、7、11、13等。2是唯一的偶數(shù)素?cái)?shù)，其他偶數(shù)（如4、6、8等）均不是素?cái)?shù)，因?yàn)樗鼈兛梢员?整除。

素?cái)?shù)的性質(zhì)

• 唯一分解定理：任何大于1的自然數(shù)都可以唯一地分解為素?cái)?shù)的乘積。
• 無(wú)限性：素?cái)?shù)有無(wú)限多個(gè)，這一結(jié)論最早由歐幾里得證明。
• 分布規(guī)律：素?cái)?shù)在自然數(shù)中的分布不均勻，但隨著數(shù)值增大，素?cái)?shù)出現(xiàn)的頻率逐漸降低（素?cái)?shù)定理）。

判斷素?cái)?shù)的方法

試除法：根據(jù)上面對(duì)素?cái)?shù)性質(zhì)的理解，我們可以聯(lián)想到最簡(jiǎn)單的判斷方式，就是一個(gè)數(shù)，從1開(kāi)始往后一個(gè)數(shù)一個(gè)數(shù)的去做除法，直到它本身，如果都沒(méi)有能被除盡(沒(méi)有余數(shù))，則這個(gè)數(shù)就是素?cái)?shù)

public static boolean isPrime(int n) {//n表示傳入需要判斷的數(shù)
    if (n <= 1) {//如果小于1不是素?cái)?shù)，直接返回
        return false;
    }
    for (int i = 2; i < n; i++) {//從除數(shù)2開(kāi)始往后除，一直到n本身
        if (n % i == 0) {//如果n能被i整除(無(wú)余數(shù)),則這個(gè)數(shù)不是素?cái)?shù)
            return false;
        }
    }
    //當(dāng)所有的數(shù)字都除完了，沒(méi)有一個(gè)i能整除n，則是素?cái)?shù)
    return true;
}
 

通過(guò)上面的代碼可以做到素?cái)?shù)的判斷，但是這樣的判斷效率非常的慢，如果需要判斷的素?cái)?shù)非常的大，一個(gè)一個(gè)的從1開(kāi)始除，則需要浪費(fèi)很多時(shí)間，我們可以引入一個(gè)變量count來(lái)計(jì)數(shù)一下，總共

進(jìn)行了多少次循環(huán)

public static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    int count = 0;  // 初始化計(jì)數(shù)器
    for (int i = 2; i < n; i++) {
        count++;     // 每次循環(huán)遞增計(jì)數(shù)器
        if (n % i == 0) {
            System.out.println("count: " + count);  // 輸出循環(huán)次數(shù)
            return false;
        }
    }
    System.out.println("count: " + count);  // 輸出循環(huán)次數(shù)
    return true;
}
 

例如我們需要判斷52087這個(gè)數(shù)字是否為素?cái)?shù)，可以看到count如下：

count: 50285

可以看到需要循環(huán)的次數(shù)非常的多，那么我們有沒(méi)有可以進(jìn)行優(yōu)化的方法呢？

有的兄弟，有的

方法優(yōu)化

上述方法可以進(jìn)一步優(yōu)化，減少循環(huán)次數(shù)：

public static boolean isPrime(int n) {
        int count = 0;
        for (int i = 2; i <= Math.sqrt(n) ; i++) {//Math.sqrt(n)指的是n開(kāi)根號(hào)
            count++;
            if (n % i == 0) {
                return false;
            }
        }
        System.out.println(count);
        return true;

在這個(gè)方法中，我們可以看到在for循環(huán)中除數(shù)的結(jié)束循環(huán)發(fā)生了變化，在上一個(gè)方法中結(jié)束的條件是循環(huán)到判斷數(shù)n本身的位置，在這個(gè)方法中則是變成了√n，這個(gè)怎么去理解呢？

我們可以觀察上圖，四個(gè)數(shù)中的因子，都是成對(duì)出現(xiàn)的，我們以36為例子，36的平方根是6，

我們可以發(fā)現(xiàn)，左邊綠色部分的數(shù)，都是小于平方根的，右邊藍(lán)色部分的數(shù)都是大于平方根的，平方根把因子平均分為了兩組，且兩組都是一一對(duì)應(yīng)的，那我們就可以只需要看一邊就能判斷這個(gè)數(shù)是否為素?cái)?shù)了，不需要再去看大的數(shù)目了，所以這時(shí)候循環(huán)結(jié)束條件的最大值就可以定為√n，直接省略掉了一半需要判斷的數(shù)目，提高了效率

需要注意的是此處的判斷條件從＜變成了＜=，因?yàn)槲覀冞€需要判斷平方根本身

通過(guò)上述方法，便可以輕松的判斷一個(gè)數(shù)是否為素?cái)?shù)啦

當(dāng)然還有更進(jìn)一步的優(yōu)化

進(jìn)一步優(yōu)化：跳過(guò)偶數(shù)

除2外，素?cái)?shù)均為奇數(shù)，所以因子就不會(huì)有偶數(shù)了，可跳過(guò)偶數(shù)除數(shù)。

public static boolean isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i <= Math.sqrt(n); i += 2) {//每次+2，跳過(guò)除數(shù)為偶數(shù)的判斷
        if (n % i == 0) return false;
    }
    return true;
}
 

效果：循環(huán)次數(shù)再減半。

總結(jié)

• 基礎(chǔ)方法：簡(jiǎn)單但低效，適合教學(xué)理解。
• 平方根優(yōu)化：顯著減少循環(huán)次數(shù)，適用于多數(shù)場(chǎng)景。
• 跳過(guò)偶數(shù)：進(jìn)一步提升效率，尤其適合大數(shù)判斷。

到此這篇關(guān)于Java中判斷一個(gè)數(shù)是否為素?cái)?shù)(質(zhì)數(shù))的文章就介紹到這了,更多相關(guān)Java判斷素?cái)?shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論