13195 sayısının asal çarpanları 5, 7, 13 ve 29’dur.
600851475143 sayısının en büyük asal çarpanı nedir?
Algoritma:
Bu soruyu çözebilmek için evvela asal çarpanın ne olduğunu anlamak gerekir. Asal çarpanlar, bir sayıyı bölebilen asal sayılardır. Tanımından da anlaşılacağı üzere bulacağımız sayılar asal olmalı. O hâlde amacımız, ilgili sayıyı en küçük asal sayıdan başlayarak böldürmek, eğer bölünebiliyorsa ilgili sayıyı başta tanımlayacağımız bir listenin içerisine eklemektir. Sayıyı bu asal sayıya bölünebildiği kadar böldürüp küçülteceğiz ve bölünemediği an bir sonraki sayı ile devam edeceğiz. Buradaki amaç, asal sayının tüm çarpanlarını sayının içerisinden söküp atmak. Böylece bölenleri arttırdığımızda, sayıyı bölebilen sayıların yine asal olduklarını göreceğiz.
Misal; 2 sayısını büyük sayıdan söküp attığımızda bu sayının 2*2=4‘e bölünme olasılığı ortadan kalkmış oluyor. Yani asal sayıların katlarını sayıdan kurtarmış olup, bir sonraki bölenin asal olacağını garantilemiş oluyoruz.
Amacımız en son 1 rakamına ulaşmak.
- Ölçmek istediğimiz sayıyı alalım.
- Sayıyı en küçük asal sayıya böldürelim. (Bu durumda 2)
- Eğer bölünüyorsa listeye ilgili asal sayıyı ekleyelim.
- Sayının bölünebildiği kadar şu anki asal sayıya bölerek bu sayıyı küçültelim.
- Sayı bölünemez olduğunda bölen sayısını arttıralım ve 2. adımdan itibaren tekrarlayalım.
- 1 rakamına ulaştığımızda programı sonlandıralım.
- Dizinin en büyük elemanını ya da duruma göre en son elemanını yazdıralım.
Akış Şeması:
Koda Dökme (Python):
import time
start=time.time()
def zaza(sayi):
dizi = []
for i in range(2, sayi+1):
if sayi%i==0:
dizi.append(i)
while sayi%i==0:
sayi=sayi/i
if sayi==1:
break
return dizi[-1]
print(zaza(600851475143))
end=time.time()
print(end-start)
