Bagaimanakah anda boleh mengoptimumkan algoritma brute-force untuk mencari faktor utama dalam Python?

Mencari Faktor Utama dalam Python: Panduan Komprehensif

Menentukan faktor perdana ialah tugas asas dalam teori nombor. Satu pendekatan untuk mencari faktor utama terbesar adalah melalui algoritma brute-force. Walau bagaimanapun, tidak semua algoritma dicipta sama.

Algoritma Brute-Force

Satu algoritma yang biasa digunakan melibatkan ujian nombor secara berperingkat sehingga nombor ditemui yang membahagi sama rata kepada yang asal nombor. Mari kita pertimbangkan contoh kod:

n = 600851475143
i = 2
while i * i < n:
    while n % i == 0:
        n = n / i
    i = i + 1

print(n)

Kod ini mencari faktor perdana terbesar 600851475143. Walau bagaimanapun, ia mengalami ketidakcekapan, mengambil masa kira-kira 0.01 saat untuk diselesaikan.

Dioptimumkan Algoritma Brute-Force

Versi algoritma brute-force yang dipertingkat boleh mengurangkan masa jalan dengan ketara:

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

Algoritma ini ditamatkan sebaik sahaja i melebihi punca kuasa dua n , yang berkesan menghapuskan ujian banyak nombor yang tidak perlu. Akibatnya, masa jalan dikurangkan secara mendadak, diselesaikan dalam kira-kira 388 mikrosaat untuk input yang sama.

Pemfaktoran Perdana Lengkap

Jika matlamatnya adalah untuk mendapatkan perdana lengkap pemfaktoran nombor, sedikit pengubahsuaian pada algoritma diperlukan:

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

Algoritma ini mengekalkan senarai yang dipanggil 'faktor' yang menyimpan faktor perdana semasa ia ditemui. Apabila n lebih besar daripada 1 pada penghujung, ia menunjukkan faktor perdana akhir, yang kemudiannya ditambahkan pada senarai.

Kesimpulannya, memilih algoritma pemfaktoran perdana yang cekap adalah penting untuk prestasi. Algoritma brute-force yang dioptimumkan memberikan peningkatan yang ketara dalam kelajuan, manakala algoritma pemfaktoran lengkap menawarkan pemfaktoran perdana penuh bagi nombor tertentu.

Atas ialah kandungan terperinci Bagaimanakah anda boleh mengoptimumkan algoritma brute-force untuk mencari faktor utama dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!