Python Kodun daha verimli olması için ne yapılabilir?

Ahmsef · 15 Şubat 2025

Merhaba arkadaşlar. Python öğrenmeye başladım ve öğrendiklerimi project Euler'e uygulamak istedim. Project EU'ler problemlerinin 1 ve ikisini yaptım ve 3'ü de yaptım fakat sayı çok büyük olduğundan şu an hala hesaplamadı. Hatta ChatGPT'den test ettim kod doğru fakat o da verimli olmadığını söyledi. Soru 600851475143 sayısının en büyük asal çarpanını bulmamızı istiyor.
Yazdığım kod:

Python:

a = []
for i in range(1, 600851475143):
 if 600851475143 % i == 0:
 a.append(i)

def isprime(n):
 for i in range(2, int(n**0.5)+1):
 if n % i == 0:
 return False.
 return True.

b = []
for i in a:
 if isprime(i):
 b.append(i)

print(max(b))

RaSGooL · 15 Şubat 2025

İlk döngüden çıkabilirse bulacak : )
Tam bölenlerin listesi gerçekten lazım mı? Basit bir matematik ile bunu aşabilirsin gibi geliyor.
Temel şu bilgiyi önden vereyim (sende uygulamışsın. n**0.5) en büyük asal çarpan, o sayının karekökünü aşamaz.
2. bilgiyi verelim; asal çarpan arıyorsan tek sayılar üzerinden ilerleyeceksin.

Ee asal çarpan arıyoruz. Asal dediğin tek olur. Sayı çift ise önce tek olana dek 2ye böl tek sayıyı bul bunun üzerinden ilerle.
Tek sayı elde etmek istiyorsan tek sayı ile çarpacaksın. O zaman 3 den başlayarak, yukarıdaki max değere (sayının karekökü) kadar 2şer 2şer gidelim.
sayıyı index e böl. 0 ise bu aradığın değer olabilir. at köşeye.
Mantıken bu tarz bir bölme sonucunda asal çarpanına ulaşmış olacaksın. Asal çarpan hiçbir sayıya bölünmediği için en son kendisi kalacak. Tek performans kayıp kısmı o sayıya ulaşana kadar loop olması. Yukarıdaki sayı için loop sayısı sanırım yaklaşık; 3 bin falandır. Temel bir dilde 3 bin döngü hiçbir şey. C de nano saniyede verir onu. Python da performans aramadığım için o ne kadar hızlı çalışır bilemem.

Karışık anlatmış olabilirim. Temel mantık, matematiğin kendisi.

Son olarak senin kodun yavaşlığı şu; o^3 (big o notation) zamanda bulmaya çalışıyorsun. Birde python eklenince, uzun sürmesi gayet normal.
o^3 = ilk for > a array loop > isPrime loop

Ahmsef · 16 Şubat 2025

RaSGooL dedi:
İlk döngüden çıkabilirse bulacak: )
Tam bölenlerin listesi gerçekten lazım mı? Basit bir matematik ile bunu aşabilirsin gibi geliyor.
Temel şu bilgiyi önden vereyim (sende uygulamışsın. N**0.5) en büyük asal çarpan, o sayının karekökünü aşamaz.
2. bilgiyi verelim; asal çarpan arıyorsan tek sayılar üzerinden ilerleyeceksin.

Ee asal çarpan arıyoruz. Asal dediğin tek olur. Sayı çift ise önce tek olana dek 2ye böl tek sayıyı bul bunun üzerinden ilerle.
Tek sayı elde etmek istiyorsan tek sayı ile çarpacaksın. O zaman 3'ten başlayarak, yukarıdaki Max değere (sayının karekökü) kadar 2'şer 2'şer gidelim.
Sayıyı index e böl. 0 ise bu aradığın değer olabilir. At köşeye.
Mantıken bu tarz bir bölme sonucunda asal çarpanına ulaşmış olacaksın. Asal çarpan hiçbir sayıya bölünmediği için en son kendisi kalacak. Tek performans kayıp kısmı o sayıya ulaşana kadar loop olması. Yukarıdaki sayı için loop sayısı sanırım yaklaşık; 3 bin falandır. Temel bir dilde 3 bin döngü hiçbir şey. C de nano saniyede verir onu. Python da performans aramadığım için o ne kadar hızlı çalışır bilemem.

Karışık anlatmış olabilirim. Temel mantık, matematiğin kendisi.

Son olarak senin kodun yavaşlığı şu; o^3 (big o notation) zamanda bulmaya çalışıyorsun. Bir de Python eklenince, uzun sürmesi gayet normal.
O^3 = ilk for > a array loop > isPrime loop

Hocam anladığım şey sayısı tek sayıya çevirip tek sayılara bölüp o bölenlerden asal olanları bulup en büyüğünü bulmak. Bu sanırsam 2'nin üssü mesela 2 ise 3 kat azaltacak çarpan sayısını. Bu şekilde daha hızlıca hesaplayacak. Bence siz kodu yazın ben öyle anlarım. Python'u sadece başlangıç düzeyinde biliyorum.

RaSGooL · 16 Şubat 2025

Kod şöyle bir şey;

JavaScript:

let num = 600851475143;
let primeFactor = 2; // min 2 olabilir.

while(num % 2 == 0) num /= 2;
// num tek sayı olarak gelecek artık.

// Karekok ve tek sayı muhabbeti. İlk mesajımda temel bilgi olarak yazmıştım.
for(let i = 3; i<= Math.sqrt(num); i+=2) {
    while(num % i == 0) {
        primeFactor = i; // Son böldüğümüz değeri köşeye atalım. Asal sayımız bu olabilir.
        num /= i;
    }
}

if(num > 2) {
    // eğer 2 den büyük bir sayı kalıyorsa, bu en büyük asal çarpanıdır. Hiçbir şeye bölünmemiş.
    primeFactor = num;
}

console.log("En büyük asal çarpan: ", num);

JavaScript ile yazdım. Dilden bağımsız bir algoritma zaten. Dilediğin dilde yazarsın. Ayrıca kodu testte etmedim.

bitwise · 16 Şubat 2025

Ilk buldugun asal sayida cevabi da bulmus oluyorsun zaten, gereksiz fazla primality testi yapmissin. Recursion dusunebilirsin.

Kod da vereyim havada kalmasin, edge test etmedim.

Python:

from functools import lru_cache
import math

@lru_cache(None) # lru asal hesaplamada iyidir
def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    limit = int(math.sqrt(n))
    for i in range(5, limit + 1, 2):
        if n % i == 0:
            return False
    return True

def prm_factor(c: int) -> int:
    if c < 2:
        raise Exception("c>=2 aksiyom")

    start = int(math.sqrt(c))
    if start % 2 == 0:
        start -= 1

    for g in range(start, 1, -2):
        if c % g == 0 and is_prime(g):
            return g # ilk match gg
    return c if is_prime(c) else None # sayinin kendisi asal olabilir

print(prm_factor(600851475143))

Ahmsef · 16 Şubat 2025

bitwise dedi:

Ilk buldugun asal sayida cevabi da bulmus oluyorsun zaten, gereksiz fazla primality testi yapmissin. Recursion dusunebilirsin.

Kod da vereyim havada kalmasin, Edge test etmedim.

Python:

from functools import lru_cache
import math

@lru_cache(None) # lru asal hesaplamada iyidir
def is_prime(n: int) -> bool:
 if n < 2:
 return False
 if n in (2, 3):
 return True
 if n % 2 == 0 or n % 3 == 0:
 return False
 limit = int(math.sqrt(n))
 for i in range(5, limit + 1, 2):
 if n % i == 0:
 return False
 return True

def prm_factor(c: int) -> int:
 if c < 2:
 raise Exception("c>=2 aksiyom")

 start = int(math.sqrt(c))
 if start % 2 == 0:
 start -= 1

 for g in range(start, 1, -2):
 if c % g == 0 and is_prime(g):
 return g # ilk match gg
 return c if is_prime(c) else None # sayinin kendisi asal olabilir

print(prm_factor(600851475143))

Merhaba hocam. Kendim kütüphane olmadan kısa sürede çözümü öğrendim.
Kod bu:

Python:

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def largestprimefactor(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n = n // 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        while n % i == 0:
            if isprime(i):
                a.append(i)
            n = n // i
    if n > 2:
        a.append(n)
    return max(a)

print(largestprimefactor(600851475143))

Bu arada temel düzey Python bildikten sonra nasıl ilerlemeliyim? Muhtemelen önümdeki 2 sene boyunca YKS odaklı olacağımdan bu kodlama işi bayağı arka planda kalacak ama.

Python Kodun daha verimli olması için ne yapılabilir?

Ahmsef

Hectopat

RaSGooL

Kilopat

Ahmsef

Hectopat

RaSGooL

Kilopat

bitwise

Gigapat

Ahmsef

Hectopat