Mengapa kita memeriksa hingga akar kuadrat dari bilangan prima untuk menentukan apakah bilangan prima?

Untuk menguji apakah suatu bilangan prima atau tidak, mengapa kita harus menguji apakah bilangan hanya dapat dibagi hingga akar kuadrat dari bilangan itu?

Jika suatu bilangan nbukan bilangan prima, maka bilangan dapat diperhitungkan menjadi dua faktor adan b:

n = a * b

Sekarang adan btidak bisa keduanya lebih besar dari akar kuadrat n, karena itu produknya a * bakan lebih besar dari sqrt(n) * sqrt(n) = n. Jadi dalam faktorisasi apa pun n, setidaknya salah satu faktor harus lebih kecil dari akar kuadrat n, dan jika kita tidak dapat menemukan faktor apa pun yang kurang dari atau sama dengan akar kuadrat, nharus menjadi prima.

Katakanlah kalau m = sqrt(n)begitu m × m = n. Sekarang jika nbukan bilangan prima maka ndapat ditulis sebagai n = a × b, jadi m × m = a × b. Perhatikan bahwa itu madalah bilangan real sedangkan n, adan bmerupakan bilangan alami.

Sekarang ada 3 kasus:

1. a> m ⇒ b <m
2. a = m ⇒ b = m
3. a <m ⇒ b> m

Dalam semua 3 kasus min(a, b) ≤ m,. Karena itu jika kita mencari sampai m, kita pasti menemukan setidaknya satu faktor n, yang cukup untuk menunjukkan yang ntidak prima.

Karena jika suatu faktor lebih besar dari akar kuadrat dari n, faktor lain yang akan berlipat ganda dengan itu menjadi n harus kurang dari akar kuadrat dari n.

Penjelasan yang lebih intuitif adalah: -

Akar kuadrat dari 100 adalah 10. Katakanlah axb = 100, untuk berbagai pasangan a dan b.

Jika a == b, maka keduanya sama, dan merupakan akar kuadrat dari 100, tepatnya. Yaitu 10.

Jika salah satu dari mereka kurang dari 10, yang lain harus lebih besar. Misalnya, 5 x 20 == 100. Yang satu lebih besar dari 10, yang lain kurang dari 10.

Memikirkan axb, jika salah satu turun, yang lain harus mendapatkan kompensasi lebih besar, sehingga produk tetap 100. Mereka berputar di sekitar akar kuadrat.

Akar kuadrat dari 101 adalah sekitar 10,049875621. Jadi, jika Anda menguji angka 101 untuk primality, Anda hanya perlu mencoba bilangan bulat hingga 10, termasuk 10. Tapi 8, 9, dan 10 bukan prima, jadi Anda hanya perlu menguji hingga 7, yaitu utama.

Karena jika ada sepasang faktor dengan salah satu angka lebih besar dari 10, yang lain dari pasangan harus kurang dari 10. Jika yang lebih kecil tidak ada, tidak ada faktor pencocokan yang lebih besar dari 101.

Jika Anda menguji 121, akar kuadratnya adalah 11. Anda harus menguji bilangan bulat utama 1 hingga 11 (inklusif) untuk melihat apakah bilangan masuknya merata. 11 masuk 11 kali, jadi 121 tidak prima. Jika Anda berhenti di 10, dan tidak menguji 11, Anda akan melewatkan 11.

Anda harus menguji setiap bilangan bulat utama lebih besar dari 2, tetapi kurang dari atau sama dengan akar kuadrat, dengan asumsi Anda hanya menguji angka ganjil.

`

Misalkan nbukan bilangan prima (lebih besar dari 1). Jadi ada angka adan bsemacamnya

n = ab      (1 < a <= b < n)

Dengan mengalikan relasi a<=bdengan adan bkita mendapatkan:

a^2 <= ab
 ab <= b^2

Oleh karena itu: (perhatikan itu n=ab)

a^2 <= n <= b^2

Oleh karena itu: (Catat itu adan bpositif)

a <= sqrt(n) <= b

Jadi, jika angka (lebih dari 1) tidak prima dan kami menguji pembagian hingga akar kuadrat dari angka tersebut, kami akan menemukan salah satu faktor.

Misalkan bilangan bulat yang diberikan Ntidak prima,

Maka N dapat difaktorkan menjadi dua faktor adan b, 2 <= a, b < Nsedemikian rupa N = a*b. Jelas, keduanya tidak bisa lebih besar daripada sqrt(N)secara bersamaan.

Mari kita asumsikan tanpa kehilangan keumuman yang alebih kecil.

Sekarang, jika Anda tidak dapat menemukan pembagi Nkepemilikan di dalam rentang tersebut [2, sqrt(N)], apa artinya itu?

Ini berarti bahwa Ntidak memiliki pembagi [2, a]sebagai a <= sqrt(N).

Oleh karena itu, a = 1dan b = nkarenanya definisi, Nadalah prima .

...

Bacaan lebih lanjut jika Anda tidak puas:

Banyak kombinasi yang berbeda (a, b)dimungkinkan. Katakanlah mereka adalah:

(a ₁ , b ₁ ), (a ₂ , b ₂ ), (a ₃ , b ₃ ), ....., (a _k , b _k ). Tanpa kehilangan umum, menganggap _saya <b _i , 1<= i <=k.

Sekarang, untuk dapat menunjukkan yang Ntidak prima itu cukup untuk menunjukkan bahwa tidak ada _{i yang} dapat difaktorkan lebih lanjut. Dan kita juga tahu bahwa _i <= sqrt(N)dan dengan demikian Anda perlu memeriksa sampai sqrt(N)mana yang akan mencakup semua _i . Dan karenanya Anda akan dapat menyimpulkan apakah Nprima atau tidak .

...

Itu semua benar-benar hanya penggunaan dasar Factorization dan Square Roots.

Ini mungkin tampak abstrak, tetapi dalam kenyataannya ia hanya terletak pada fakta bahwa faktorial maksimum yang mungkin bukan-bilangan prima harus menjadi akar kuadratnya karena:

sqrroot(n) * sqrroot(n) = n.

Mengingat bahwa, jika ada bilangan bulat di atas 1dan di bawah atau di atas untuk sqrroot(n)membagi secara merata n, maka ntidak bisa menjadi bilangan prima.

Contoh kode semu:

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}

Jadi untuk memeriksa apakah angka N adalah Prime atau bukan. Kita hanya perlu memeriksa apakah N dapat dibagi dengan angka <= SQROOT (N). Ini karena, jika kita memasukkan faktor N ke dalam 2 faktor, katakanlah X dan Y, yaitu. N = X Y. Setiap X dan Y tidak boleh kurang dari SQROOT (N) karena itu, X Y <N Masing-masing X dan Y tidak boleh lebih besar dari SQROOT (N) karena dengan begitu, X * Y> N

Oleh karena itu satu faktor harus kurang dari atau sama dengan SQROOT (N) (sedangkan faktor lainnya lebih besar dari atau sama dengan SQROOT (N)). Jadi untuk memeriksa apakah N adalah Prime, kita hanya perlu memeriksa angka-angka itu <= SQROOT (N).

Katakanlah kita memiliki angka "a", yang bukan bilangan prima [bukan bilangan prima / gabungan berarti - bilangan yang dapat dibagi secara merata dengan bilangan selain 1 atau itu sendiri. Misalnya, 6 dapat dibagi secara merata dengan 2, atau dengan 3, serta oleh 1 atau 6].

6 = 1 × 6 atau 6 = 2 × 3

Jadi sekarang jika "a" tidak prima maka dapat dibagi dengan dua angka lain dan katakanlah angka-angka itu adalah "b" dan "c". Yang berarti

a = b * c.

Sekarang jika "b" atau "c", salah satu dari mereka lebih besar dari akar kuadrat dari "a" dari perkalian "b" & "c" akan lebih besar dari "a".

Jadi, "b" atau "c" selalu <= akar kuadrat dari "a" untuk membuktikan persamaan "a = b * c".

Karena alasan di atas, ketika kami menguji apakah suatu bilangan prima atau tidak, kami hanya memeriksa sampai akar kuadrat dari angka tersebut.

Dengan diberi nomor berapa pun n, maka salah satu cara untuk menemukan faktor-faktornya adalah dengan mendapatkan akar kuadratnya p:

sqrt(n) = p

Tentu saja, jika kita mengalikannya psendiri, maka kita kembali n:

p*p = n

Itu dapat ditulis ulang sebagai:

a*b = n

Mana p = a = b. Jika ameningkat, maka bberkurang untuk mempertahankan a*b = n. Karena itu, padalah batas atas.

Pembaruan: Saya membaca lagi jawaban ini hari ini dan menjadi lebih jelas bagi saya. Nilai ptidak selalu berarti bilangan bulat karena jika itu, maka ntidak akan menjadi bilangan prima. Jadi, pbisa berupa bilangan real (yaitu, dengan pecahan). Dan bukannya melalui seluruh jajaran n, sekarang kita hanya perlu melewati seluruh jajaran p. Yang lainnya padalah salinan cermin sehingga efeknya kami membagi dua kisaran. Dan kemudian, sekarang saya melihat bahwa kita benar-benar dapat melanjutkan melakukan kembali square rootdan melakukannya puntuk lebih jauh setengah kisaran.

Biarkan n menjadi non-prima. Oleh karena itu, ia memiliki setidaknya dua faktor bilangan bulat lebih besar dari 1. Biarkan f menjadi yang terkecil dari faktor-faktor tersebut. Misalkan f> sqrt n. Maka n / f adalah integer LTE sqrt n, jadi lebih kecil dari f. Oleh karena itu, f tidak dapat menjadi faktor terkecil n. Reductio ad absurdum; Faktor terkecil n harus LTE sqrt n.

Setiap angka komposit adalah produk bilangan prima.

Katakanlah n = p1 * p2, di mana p2 > p1dan mereka adalah bilangan prima.

Jika n % p1 === 0 kemudian n adalah angka komposit.

Jika n % p2 === 0kemudian tebak apa n % p1 === 0juga!

Jadi tidak mungkin kalau n % p2 === 0tapi n % p1 !== 0pada saat bersamaan. Dengan kata lain, jika bilangan komposit n dapat dibagi rata dengan p2, p3 ... pi (faktor yang lebih besar), ia harus dibagi dengan faktor terendah p1 juga. Ternyata faktor terendah p1 <= Math.square(n)selalu benar.

Untuk menguji keutamaan angka, n , orang akan mengharapkan loop seperti berikut di tempat pertama:

bool isPrime = true;
for(int i = 2; i < n; i++){
    if(n%i == 0){
        isPrime = false;
        break;
    }
}

Apa loop di atas tidak adalah ini: untuk diberikan 1 <i <n , itu memeriksa apakah n / i adalah bilangan bulat (meninggalkan sisa 0). Jika ada i di mana n / i adalah bilangan bulat, maka kita dapat yakin bahwa n bukan bilangan prima, pada saat mana loop berakhir. Jika tanpa i, n / i adalah bilangan bulat, maka n adalah bilangan prima.

Seperti halnya setiap algoritma, kami bertanya: Bisakah kita melakukan yang lebih baik?

Mari kita lihat apa yang terjadi di loop di atas.

Urutan i pergi: i = 2, 3, 4, ..., n-1

Dan urutan bilangan bulat cek: j = n / i, yaitu n / 2, n / 3, n / 4, ..., n / (n-1)

Jika untuk beberapa i = a, n / a adalah bilangan bulat, maka n / a = k (integer)

atau n = ak, jelas n> k> 1 (jika k = 1, maka a = n, tetapi saya tidak pernah mencapai n; dan jika k = n, maka a = 1, tetapi saya mulai dari bentuk 2)

Juga, n / k = a, dan seperti yang dinyatakan di atas, a adalah nilai i jadi n> a> 1.

Jadi, a dan k keduanya bilangan bulat antara 1 dan n (eksklusif). Karena, saya mencapai setiap bilangan bulat dalam rentang itu, pada beberapa iterasi i = a, dan pada beberapa iterasi lainnya i = k. Jika tes primality dari n gagal untuk min (a, k), itu juga akan gagal untuk maks (a, k). Jadi kita perlu memeriksa hanya satu dari dua kasus ini, kecuali min (a, k) = maks (a, k) (di mana dua cek dikurangi menjadi satu) yaitu, a = k, di mana titik a * a = n, yang menyiratkan a = sqrt (n).

Dengan kata lain, jika uji keutamaan n gagal untuk beberapa i> = sqrt (n) (yaitu, maks (a, k)), maka itu juga akan gagal untuk beberapa i <= n (yaitu, min (a , k)). Jadi, akan cukup jika kita menjalankan tes untuk i = 2 hingga sqrt (n).