En Verimli Çarpan Bulma Algoritması

Question

Project Euler'de bir soruyu çözerken aklıma geldi bu olay. Soru şu; $500$'den fazla böleni olan ilk üçgensel sayı kaçtır. Kullandığım algoritma da şöyle, önce bir üçgensel sayı üreticisi fonksiyon tanımladım, ardından üreticiden aldığım çıktıların karekökünden küçük bütün çarpanların sayısını kaba kuvvet ile bulup ikiyle çarptım, karekökünden küçük bütün çarpanlara karşılık karekökünden büyük bir çarpan olması mantığını kullanarak. Bir de sayı tam kare ise 1 eklemek lazım tabi. Fakat bu yöntem bana yeterince verimli gelmedi, 3.9 saniye sürüyor cevabı bulması. Çarpan sayısı ve direkt bütün çarpanları bulan en verimli algoritma nedir günümüzün standartlarında?

Comments

kodunuzu paylasir misiniz ?

---

Üretici fonksiyondan çıkan sayının asal çarpanlarının kuvvetlerini bulduran başka bir fonksiyon daha tanımlasak. Daha sonra da bu kuvvetleri matematiksel olarak bildiğimiz pozitif çarpan sayısı bulma formülünde yerine yazıp sonucun 500 den büyük kalıp kalmadığını belirleyebiliriz.

---

denemelerini paylaşmanız gerekmekte.

---

@ece_celik pozitif carpan sayisi bulma formulu nedir?

 

Genel olarak asal carpanlari da bulmak zor bir problem degil mi ?  Kaba kuvvet disinda bir yol yok bildigim kadari ile (eger kuantum bilgisayariniz yoksa)

---

def TriangleNumber(x):
    return int(x*(x+1)/2)


def Factorization(x):
    sqrt = x**(1/2)
    if sqrt == sqrt//1:
        factors = []
        for numbers in range (1,int(sqrt+1)):
            if sqrt%numbers == 0:
                factors.append(numbers)
                factors.append(x/numbers)
                factors.sort()
    else:
        factors = []
        for numbers in range(1,(int(sqrt//1))):
            if x%numbers == 0:
                factors.append(numbers)
                factors.append(int(x/numbers))
                factors.sort()
                
                
    return factors , len(factors)
    

for i in range (0,20000):
    if Factorization(TriangleNumber(i))[1] >= 500:
        print((Factorization(TriangleNumber(i))),TriangleNumber(i)) 
        break

 

---

Böyle yazdım, en düzgünü olmayabilir :). Bir de asal çarpanların kuvvetlerini bulma işi büyük sayılarda çok sıkıntı çıkarır bence.

---

Henuz tam inceleyemedim ama Factorization fonksiyonunda gercekten factors listesini sort etmek gerekiyor mu her dongunun icinde ? Her faktor icin $n \log n $ kadar isleme sebep oluyor bu durum. If Else in gerekliligine de cok ikna olamadim. Iste oldugum icin deneyemiyorum ama eve gidince bakacagim