Bagaimana untuk mencari Faktor Perdana Terbesar Nombor dalam Python?

Mencari Faktor Perdana dalam Python

Tugas biasa dalam teori nombor ialah mencari faktor perdana bagi suatu nombor. Satu kaedah yang berpotensi adalah dengan hanya membahagikan nombor dengan setiap nombor lain daripada 2 ke tingkat punca kuasa duanya, memeriksa sama ada bakinya ialah 0. Walau bagaimanapun, pendekatan ini boleh menjadi mahal dari segi pengiraan.

Seorang yang lebih cekap- Algoritma daya khusus untuk mencari faktor perdana terbesar bagi sesuatu nombor dibentangkan di bawah:

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

Algoritma ini berfungsi dengan melelaran semua nombor sehingga punca kuasa dua nombor yang diberikan. Bagi setiap nombor, ia menyemak sama ada nombor itu adalah faktor nombor yang diberikan dan membahagikan nombor itu dengan faktor jika ia. Algoritma diteruskan sehingga nombor itu tidak lagi boleh dibahagikan dengan mana-mana nombor dalam julat dan nombor yang selebihnya ialah faktor perdana terbesar.

<code class="python">largest_prime_factor(600851475143)
# Output: 6857

Sebagai alternatif, untuk mencari semua faktor perdana bagi suatu nombor:

<code class="python">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</code>

Atas ialah kandungan terperinci Bagaimana untuk mencari Faktor Perdana Terbesar Nombor dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!