Bir sayının en büyük asal çarpanı hesaplama için en iyi yaklaşım nedir?

En verimli şu: olacağını düşünüyorum

1. En temiz bir şekilde bölen asal sayı bulmak
2. Eğer bölünme sonucu asal olup olmadığını kontrol edin
3. Değilse, bir sonraki en düşük buluyorum
4. 2'ye geçin.

Bu varsayım küçük asal faktörleri hesaplamak için daha kolay olma kurdum. Bu konuda haklı mı? Diğer yaklaşımlar içine bakmak gerekir?

Edit: şimdi fark ettim bu benim yaklaşım beyhude varsa fazla 2 önemli faktör oynamak, yana adım 2 başarısız sonucu bir ürünün iki asal sayılar, bu nedenle bir özyinelemeli algoritma gerekli.

Tekrar Düzenle: Ve şimdi bende fark ettim bunu yapar hala çalışıyor, çünkü son buldu asal sayı olmalı en yüksek, bu nedenle herhangi bir daha fazla test non-prime sonucu adım 2 olur sonuç olarak daha küçük bir asal.

Aslında büyük sayılar faktörler (daha küçük olanlar için deneme bölümü gayet iyi çalışıyor) öğrenmek için daha etkili birkaç yolu vardır.

Eğer giriş sayısı iki faktör kare kökü çok yakın olduğunu çok hızlı bir yöntem Fermat factorisation olarak bilinir. Kimlik N = (a b)(a - b) = A^2 - b^2 yapar ve kolay anlamak ve uygulamaktır. Ne yazık ki genel olarak çok hızlı değil.

Faktoring sayıları 100 haneli için bilinen en iyi yöntem Quadratic sieve. Bir bonus olarak, algoritmanın bir parçası kolayca paralel işleme ile yapılır.

Duyduğum başka bir algoritma Pollard's Rho algorithm. İkinci Dereceden genel olarak Elek ama uygulamak için daha kolay gibi görünüyor kadar verimli değil.

İki faktör bir numara bölmek için nasıl karar verdikten sonra, burada bir sayının en büyük asal çarpanı bulmak için aklıma gelen en hızlı algoritma

Başlangıçta sayı depolayan bir öncelik sırası oluşturun. Her yineleme, sıradaki en yüksek sayıyı kaldırmak ve bölmek için bir girişim iki faktör (1 bu faktörlerden biri de, tabii ki izin vermeyerek). Eğer bu adım başarısız olursa, sayının asal sayı olup ve cevabını aldın! Aksi takdirde kuyruk ve tekrar içine iki faktörün ekleyin.