Rumah >pembangunan bahagian belakang >Tutorial Python >Bagaimana untuk mencari Faktor Perdana Terbesar Nombor dalam Python?

Bagaimana untuk mencari Faktor Perdana Terbesar Nombor dalam Python?

Linda Hamilton
Linda Hamiltonasal
2024-11-07 07:49:02287semak imbas

How to Find the Largest Prime Factor of a Number in 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!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn