-> 8 – 100 arası asal sayıları yazdıran algoritma:

A1) Başla
A2) i = 8
A3) Eğer TAM(i/2)*2 = i ise A8’e git
A4) Eğer TAM(i/3)*3 = i ise A8’e git
A5) Eğer TAM(i/5)*5 = i ise A8’e git
A6) Eğer TAM(i/7)*7 = i ise A8’e git
A7) i’yi ekrana yaz
A8) Eğer i = 100 ise A10’a git
A9) i = i + 1 al ve A3’e git
A10) Dur

-> Akış Şeması / Flowchart:


prime


Algoritma konusunu daha iyi kavramak için sorularını çözdüğüm projecteuler’deki bir soruyu, okulda öğrendiğimiz bir algoritma ile çözmeye çalıştım.

Soru: 2000000’dan küçük olan asal sayıların toplamını yazdırınız.

Önce 3–100, sonra 100’ün sağına 0 ekleyerek sayıyı arttırdım:

#!/usr/bin/python3.6
# created by cicek on 20.10.2018 18:50

for i in range(3,100):

	prime = 1

	for k in range(2,i):
		if i % k == 0:
			prime = 0
	if prime != 0:
		print(i)

Bu algoritma, sadece küçük sayılar için işe yarıyordu. 3–1000000 arası asal sayıları bulması dakikalar sürüyordu. Biraz iyileştirme ile bu süreyi kısaltmak istedim:

#!/usr/bin/python3.6
# created by cicek on 20.10.2018 18:50

print(2)
for i in range(3, 1000000, 2):

	prime = 1

	for k in range(2, i):
		if i % k == 0:
			prime = 0
			break

		elif (k > (i / 2)):
			break

	if prime != 0:
		print(i)

Kodun iyileştirilmiş halinde bile sayı büyüdükçe algoritmanın zorlandığını ve 2 milyonu denediğimde 10’larca dakika geçmesine rağmen sonucu bulamadığını gördüm.

İnternette biraz araştırdığımda en hızlı algoritmalardan birini denedim:

#!/usr/bin/python3.6
# created by cicek on 20.10.2018 08:09

def sumPrimes(n):
	sum, sieve = 0, ([True] * n)

	for p in range(2, n):
		if sieve[p]:
			sum += p

			for i in range(p*p, n, p):
				sieve[i] = False
	return sum

print(sumPrimes(2000000))

–> sieve dizisine n kadar True ekliyor.
–> İlk bulduğu sayı 2
–> 2’nin katlarına False atıyor.
–> Aynı şekilde 3, 5, 7… ‘yi asal olarak ekledikten sonra, katlarına False atıyor.

Böylece asal olmayanlara False atanıyor. Geriye de True, yani asal sayılar kalıyor. Böylece kodun çalışma süresi 10+ dakikadan 2- saniyeye düştü.