Asal Sayı Bulma Algoritması

• 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:

Akış Şeması / Akış Diyagramı / Flowchart

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): # between 3 and 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ü.

Originally published at bayramcicek.github.io on October 20, 2018.