Bagaimanakah algoritma brute-force mencari faktor perdana terbesar bagi sesuatu nombor, dan mengapakah ia lebih pantas daripada menguji setiap nombor?

Python Finding Prime Factors

Soalan:

Soalan dua bahagian:

1. Bolehkah anda terangkan bagaimana algoritma brute-force untuk mencari faktor perdana terbesar bagi sesuatu nombor berfungsi?
2. Mengapakah algoritma ini lebih pantas daripada algoritma yang hanya menguji setiap nombor?

Contoh Kod:

<code class="python">n = 600851475143
i = 2
while i * i < n:
    while n % i == 0:
        n = n / i
    i = i + 1

print(n)</code>

Jawapan:

1. Cara Algoritma Berfungsi:

Algoritma yang diberikan menggunakan kekerasan untuk mencari faktor perdana terbesar dengan mengulang semua nombor dari 2 hingga punca kuasa dua nombor n yang diberi. Bagi setiap nombor i, ia menyemak sama ada ia membahagi n tanpa baki. Jika ya, ia berulang kali membahagi n dengan i sehingga n tidak lagi boleh dibahagikan dengan i. Ia kemudian menambah i sebanyak 1 dan meneruskan proses. Faktor perdana terbesar ialah nilai akhir n.

2. Mengapa Algoritma Lebih Cepat:

Algoritma yang diberikan adalah lebih pantas daripada sekadar menguji setiap nombor kerana ia mengambil kesempatan daripada fakta bahawa mana-mana faktor perdana nombor akan kurang daripada atau sama dengan punca kuasa duanya. Dengan melelaran hanya sehingga punca kuasa dua n, algoritma mengurangkan bilangan calon berpotensi untuk diperiksa, meningkatkan kecekapannya dengan ketara.

Algoritma Diperbaiki:

Yang disediakan contoh kod mempunyai beberapa isu yang menghalangnya daripada mencari faktor utama terbesar dalam semua kes dengan betul. Versi algoritma yang diperbetulkan ialah:

<code class="python">def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            n //= i
        else:
            i += 1
    return n</code>

Algoritma ini mencari faktor perdana terbesar dengan betul, walaupun untuk kuasa dua sempurna dan nombor dengan faktor perdana berulang.

Atas ialah kandungan terperinci Bagaimanakah algoritma brute-force mencari faktor perdana terbesar bagi sesuatu nombor, dan mengapakah ia lebih pantas daripada menguji setiap nombor?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!