Kimse inkar etmesin, herkes programlama öğrenme sürecinin bir aşamasında
asal sayı hesaplamaya çalışmıştır. Bu ilk algoritmalar, çoğu zaman
verimsiz algoritmalardır. Biraz kendi deneyimlerimden yola çıkarak,
Python'dan asal sayı hesaplama fonksiyonlarının evrim sürecinden
bahsedeceğim.
Tanımdan Gitme - Prosedürel
Asal sayıları biz birden ve kendinden başka bir sayıya kalansız
bölünemeyen sayılar olarak biliriz. Bu doğru bir tanımdır. Programlama
dilini yeni öğrenenler, ilk olarak tanımdan yola çıkan algoritmalar
yazarlar.
|
# -*- coding:utf-8 -*-
|
|
# 1000 tane asal sayı bulan program
|
|
|
|
print 2
|
|
# xrange değil henüz...
|
|
for i in range(3,1000):
|
|
|
|
bolundu = False
|
|
for j in range(2,i):
|
|
if i % j == 0:
|
|
bolundu=True
|
|
# break yok...
|
|
if bolundu == False:
|
|
print i
|
Tanımdan Gitme - Fonksiyonel
Asal sayı bulan ilk algoritmasını yazan programcılar, daha sonra bunu
bir fonksiyon haline getirmeyi ve tekrar tekrar kullanabilmeyi düşünür.
Aynı zamanda, birkaç önemli detay da algoritmaya eklenmiştir.
|
# -*- coding:utf-8 -*-
|
|
|
|
def asal(kaca_kadar):
|
|
"""Asal sayı bulan fonksiyon
|
|
Girdi olarak bir sayı alır
|
|
Bu sayıya kadar olan asal sayıları ekrana basar.
|
|
"""
|
|
if kaca_kadar < 2:
|
|
return
|
|
elif kaca_kadar == 2:
|
|
print 2
|
|
return
|
|
else:
|
|
print 2
|
|
for i in range(3,kaca_kadar):
|
|
bolundu = False
|
|
for j in range(2,i):
|
|
if i % j == 0:
|
|
bolundu=True
|
|
break
|
|
if bolundu == False:
|
|
print i
|
Fonksiyondan Liste Döndürme
Fonksiyon içinden direk ekrana değer basma karşıtı görüşler okuyan
programcı, fonksiyondan bir liste döndürür. Daha sonra listeyi ekrana
basar.
|
# -*- coding:utf-8 -*-
|
|
|
|
def asal(kaca_kadar):
|
|
"""Asal sayı bulan fonksiyon
|
|
Girdi olarak bir sayı alır
|
|
Bu sayıya kadar olan asal sayıları ekrana basar.
|
|
"""
|
|
asallar = [2]
|
|
if kaca_kadar < 2:
|
|
return None
|
|
elif kaca_kadar == 2:
|
|
return asallar
|
|
else:
|
|
for i in range(3,kaca_kadar):
|
|
bolundu = False
|
|
for j in range(2,i):
|
|
if i % j == 0:
|
|
bolundu=True
|
|
break
|
|
if bolundu == False:
|
|
asallar.append(i)
|
|
return asallar
|
|
|
|
if __name__ == "__main__":
|
|
# join kullanmak için, listedekiler str olmalı.
|
|
print "\n".join(map(str,asal(1000)))
|
|
"""
|
|
Bu aşamada map() bilinmiyorsa, list comprehension veya for döngüsü kullanılır.
|
|
print "\n".join([str(asal) for asal in asal(1000)])
|
|
for asal in asal(1000)
|
|
print asal
|
|
"""
|
Performans Kaygıları
Programcı artık algoritmasının performansını kafaya takacak aşamaya
gelmiştir. Çift sayılar artık hesaplanmaz, sayılar yarısından büyük
sayılarla bölünmeye çalışılmaz.
|
# -*- coding:utf-8 -*-
|
|
|
|
def asal(kaca_kadar):
|
|
"""Asal sayı bulan fonksiyon
|
|
Girdi olarak bir sayı alır
|
|
Bu sayıya kadar olan asal sayıları ekrana basar.
|
|
"""
|
|
asallar = [2]
|
|
if kaca_kadar < 2:
|
|
return None
|
|
elif kaca_kadar == 2:
|
|
return asallar
|
|
else:
|
|
for i in xrange(3,kaca_kadar,2):
|
|
bolundu = False
|
|
for j in xrange(3,(i/2) + 1, 2):
|
|
if i % j == 0:
|
|
bolundu=True
|
|
break
|
|
if bolundu == False:
|
|
asallar.append(i)
|
|
return asallar
|
|
|
|
if __name__ == "__main__":
|
|
# join kullanmak için, listedekiler str olmalı.
|
|
print "\n".join(map(str,asal(10000)))
|
|
"""
|
|
Bu aşamada map() bilinmiyorsa, list comprehension veya for döngüsü kullanılır.
|
|
print "\n".join([str(asal) for asal in asal(1000)])
|
|
for asal in asal(1000)
|
|
print asal
|
|
"""
|
Sadece asallarla bölmeye çalışmak
Programcı, asal sayı bulmak için, o sayıyı sadece asal sayılarla bölmeye
çalışmanın yettiğini hatırlar, bir önceki yöntemle bunu birleştirir.
|
# -*- coding:utf-8 -*-
|
|
|
|
def asal(kaca_kadar):
|
|
"""Asal sayı bulan fonksiyon
|
|
Girdi olarak bir sayı alır
|
|
Bu sayıya kadar olan asal sayıları ekrana basar.
|
|
"""
|
|
asallar = [2]
|
|
if kaca_kadar < 2:
|
|
return None
|
|
elif kaca_kadar == 2:
|
|
return asallar
|
|
else:
|
|
for i in xrange(3,kaca_kadar,2):
|
|
bolundu = False
|
|
for j in asallar:
|
|
|
|
if i % j == 0:
|
|
bolundu=True
|
|
break
|
|
if j > (i / 2):
|
|
break
|
|
if bolundu == False:
|
|
asallar.append(i)
|
|
return asallar
|
|
|
|
if __name__ == "__main__":
|
|
# join kullanmak için, listedekiler str olmalı.
|
|
print "\n".join(map(str,asal(20000)))
|
|
"""
|
|
Bu aşamada map() bilinmiyorsa, list comprehension veya for döngüsü kullanılır.
|
|
print "\n".join([str(asal) for asal in asal(1000)])
|
|
for asal in asal(1000)
|
|
print asal
|
|
"""
|
Kareköke kadar bölme
Bir sayının asal bölenleri, o sayının karekökünden büyük olamaz.
|
def asal(kaca_kadar):
|
|
"""Asal sayı bulan fonksiyon
|
|
Girdi olarak bir sayı alır
|
|
Bu sayıya kadar olan asal sayıları ekrana basar.
|
|
"""
|
|
asallar = [2]
|
|
if kaca_kadar < 2:
|
|
return None
|
|
elif kaca_kadar == 2:
|
|
return asallar
|
|
else:
|
|
for i in xrange(3,kaca_kadar,2):
|
|
bolundu = False
|
|
# karekökün aşağı yuvarlanma ihtimaline karşı, + 1 ekliyoruz.
|
|
limit = (i ** 0.5) + 1
|
|
for j in asallar:
|
|
|
|
if i % j == 0:
|
|
bolundu=True
|
|
break
|
|
if j > limit:
|
|
break
|
|
if bolundu == False:
|
|
asallar.append(i)
|
|
return asallar
|
Eratosthenes'in Elemesi
Bu yöntemde, 3'den verilen sayıya kadar olan tek sayılar bir listede
toplanır. Daha sonra, 3'er 3'er atlanarak, üzerine gelinen sayılar 0'a
eşitlenir. Böylece, 3'ün katları elenmiş olur. Daha sonra, ilk 0 olmayan
sayı kadar atlanarak üzerine gelinen sayılar 0'a eşitlenir. Böylece, o
sayının da katları elenmiş olur. Bu şekilde, en büyük sayının kareköküne
kadar devam edilir. Biraz önce bahsettiğimiz gibi, bir sayının kendi
karekökünden büyük asal böleni olamaz. Ve, bu sayının karekökü,
listedeki bütün sayıların karekökünden büyüktür. Dolayısıyla, bu sayının
kareköküne ulaşıldığında, elemeye son verilebilir.
|
# -*- coding:utf-8 -*-
|
|
|
|
def asal(kaca_kadar):
|
|
"""Asal sayı bulan fonksiyon
|
|
Girdi olarak bir sayı alır
|
|
Bu sayıya kadar olan asal sayıları ekrana basar.
|
|
"""
|
|
|
|
if kaca_kadar < 2:
|
|
return None
|
|
elif kaca_kadar == 2:
|
|
return [2]
|
|
else:
|
|
# 3,5,7...,kaca_kadar
|
|
sayilar = range(3,kaca_kadar + 1, 2)
|
|
kok = kaca_kadar ** 0.5
|
|
|
|
for i in xrange(0,len(sayilar)):
|
|
sayi = sayilar[i]
|
|
if sayi > kok:
|
|
break
|
|
if sayi:
|
|
ilk_sil_index = i + sayi
|
|
|
|
for j in xrange(ilk_sil_index,len(sayilar),sayi):
|
|
sayilar[j] = 0
|
|
|
|
|
|
|
|
return [2] + [sayi for sayi in sayilar if sayi]
|
|
|
|
if __name__ == "__main__":
|
|
# join kullanmak için, listedekiler str olmalı.
|
|
print "\n".join(map(str,asal(500)))
|
|
"""
|
|
Bu aşamada map() bilinmiyorsa, list comprehension veya for döngüsü kullanılır.
|
|
print "\n".join([str(asal) for asal in asal(1000)])
|
|
for asal in asal(1000)
|
|
print asal
|
