Gunakan skrip untuk mencari nombor perdana dalam php

Dalam sains komputer, nombor perdana merujuk kepada integer positif yang hanya boleh dibahagi dengan 1 dan dirinya sendiri. Nombor perdana boleh digunakan dalam bidang seperti penyulitan, terbitan matematik dan pengoptimuman algoritma. Dalam aplikasi praktikal, algoritma untuk mencari nombor perdana juga merupakan salah satu titik pengetahuan yang sangat penting Hari ini kita akan membincangkan cara menggunakan skrip dalam PHP untuk mencari nombor perdana.

1. Kaedah menapis

Kaedah menapis ialah algoritma klasik untuk mencari nombor perdana ialah untuk terus menapis nombor yang bukan nombor perdana dan apakah itu yang tinggal pada akhirnya ialah nombor perdana. Langkah-langkah khusus adalah seperti berikut:

1. Memulakan tatasusunan nombor perdana $prime = array(), dan letakkan nombor dari 2 hingga n (n ialah julat yang diperlukan) ke dalamnya.
2. Untuk nombor 2~sqrt(n) (sqrt(n) mewakili punca kuasa dua bagi n), tentukan sama ada ia adalah nombor perdana secara bergilir-gilir.
3. Selepas gelung tamat, baki nombor dalam tatasusunan perdana ialah semua nombor perdana.

Kod pelaksanaan adalah seperti berikut:

function sieve($n) {
    $prime = array();
    for($i = 2; $i <= $n; ++$i) {
        $prime[$i] = true;
    }
    for($i = 2; $i <= sqrt($n); ++$i) {
        if($prime[$i]) {
            for($j = $i*$i; $j <= $n; $j += $i) {
                $prime[$j] = false;
            }
        }
    }
    return array_keys(array_filter($prime));
}

2. Teorem Kecil Fermat

Teorem Kecil Fermat ialah teorem teori nombor penting yang boleh digunakan Menentukan sama ada suatu nombor adalah perdana. Teorem Kecil Fermat dinyatakan seperti berikut: Jika p ialah nombor perdana dan a ialah sebarang integer, maka a^(p-1)≡1(mod p).

Langkah-langkah khusus adalah seperti berikut:

1. Pilih nombor a secara rawak dan tentukan sama ada a dan n adalah perdana bersama Jika mereka tidak saling perdana, kembalikan palsu secara langsung.
2. Kira nilai a^(n-1) mod n, jika tidak sama dengan 1, kembalikan palsu.
3. Selepas banyak ujian, jika dua syarat di atas dipenuhi, maka n berkemungkinan menjadi nombor perdana.

Kod pelaksanaan adalah seperti berikut:

function is_prime($n) {
    if($n <= 1) {
        return false;
    }
    for($i = 0; $i < 10; ++$i) {
        $a = rand(1, $n-1);
        if(gcd($a, $n) != 1) {
            return false;
        }
        if(mod_pow($a, $n-1, $n) != 1) {
            return false;
        }
    }
    return true;
}

function gcd($a, $b) {
    return ($b == 0) ? $a : gcd($b, $a%$b);
}

function mod_pow($base, $exp, $modulus) {
    $result = 1;
    while($exp > 0) {
        if($exp % 2 == 1) {
            $result = ($result * $base) % $modulus;
        }
        $exp = $exp >> 1;
        $base = ($base * $base) % $modulus;
    }
    return $result;
}

Di atas ialah dua kaedah mencari nombor perdana menggunakan skrip dalam PHP. Perlu diingatkan bahawa kaedah saringan selalunya lebih cekap daripada Teorem Kecil Fermat apabila menyelesaikan julat besar nombor perdana.

Atas ialah kandungan terperinci Gunakan skrip untuk mencari nombor perdana dalam php. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!