Bagaimanakah kecekapan kaedah pemfaktoran perdana yang berbeza dibandingkan dalam Python?

Python: Efficient Prime Factorization

Soalan 1:
Memahami program Python sedia ada yang mengira yang terbesar faktor perdana 600851475143, dan meneroka kaedah pemfaktoran perdana alternatif.

Jawapan:
Kod yang anda temui dalam talian beroperasi dengan cekap dengan membahagikan nombor berulang kali dengan faktor perdana terkecil sehingga ia mencapai faktor perdana terbesar. Walaupun nombor itu tidak boleh dibahagikan dengan faktor perdana semasa, ia terus menambah faktor perdana.

Kaedah alternatif ialah menggunakan pendekatan brute-force:

<code class="python">def prime_factors(n):
    i = 2
    factors = []
    while i * i &lt;= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n &gt; 1:
        factors.append(n)
    return factors</code>

Fungsi ini menguji setiap nombor daripada 2 hingga punca kuasa dua nombor yang diberi untuk menentukan faktor perdananya. Walau bagaimanapun, kaedah ini kurang cekap untuk bilangan yang besar.

Soalan 2:
Membandingkan kecekapan dua coretan kod yang disediakan.

Jawapan:
Coretan kod kedua, yang hanya menambah pembilang, adalah jauh lebih perlahan kerana ia menyemak setiap integer sehingga nilai tertentu, manakala coretan kod pertama hanya menyemak faktor perdana terkecil dan segera membahagikannya, menghapuskan dengan cekap faktor itu.

Atas ialah kandungan terperinci Bagaimanakah kecekapan kaedah pemfaktoran perdana yang berbeza dibandingkan dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!