Burak IŞIKLI

Computer scientist living in Istanbul, Turkey. Data scientist at Turkcell, Traveller, Rower, Sailor

Twitter Github Linkedin Mail

Asal Sayı(Prime Number) Algoritması

Bir forumda gördüğüm konu üzerine ufak bir araştırma yaptım. Konuda asal sayıların bulma algoritmasının nasıl olacağı soruluyordu. Bu soru iki şekilde anlaşılabilir. Birincisi verilen sayının asal sayı olup olmadığı, ikincisi ise verilen sayı aralığındaki bütün asal sayıların bulunmasıdır. Öncelikle asal sayının ne olduğunu hatırlayalım.

Asal sayılar’, yalnız ve yalnız iki böleni olan doğal sayılardır. Kendisinden ve 1 sayısından başka böleni olmayan, 1’den büyük pozitif tam sayılar biçiminde de tanımlanmaktadır.(kendisinden küçük asal sayıların hiçbirine tam bölünmeyen sayılardır) Yüzden küçük asal sayılar 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 ve 97 dir. Tam listesi için burayı tıklayın.

Şimdi birinci algoritmamızı yapalım. Bu algoritmada tanımdan gidiyoruz. “Sayı kendisinden ve 1’den başka sayıya bölünemez”. Boolean fonksiyonu ve for döngüsü yardımıyla herhangi bir sayıyı bölündüğünü yakaladığımız takdirde false döndürerek asal sayı olmadığına karar veriyoruz. Bu algoritmanın çözüm karmaşıklığı O(n)’dir.

Prime.cpp

/*
 * Process:  Prime Number
 * Programmer: Burak ISIKLI
 *
 */

#include<iostream.h>

bool isPrimeNumber(long int num);

int main() {
 long int number;
 cout << "Find primes: ";
 cin >> number;

 if (isPrimeNumber(number))
 cout << endl << number << ", is a prime number" << endl;
 else
 cout << endl << number << ", isn't a prime number" << endl;

 return 0;
}

bool isPrimeNumber(long int num) {
 for (long int i = 2; i < num; i++) {
 if (num % i == 0)
 return false;
 }
 return true;
}

Bu prosesimiz bize Çözmek istediğimiz sayıyı soruyor. Öğrenmek istediğimiz sayıyı girdiğimizde sayının asal olup olmadığını söylüyor.

Peki ama bu algoritmayı daha verimli yapamaz mıyız? Elbette yapabiliriz. Eğer n sayımızın şu şekilde bir fonksiyon aralığında olduğunu düşünürsek d (1 < d < n) ve bu fonksiyonun tamamının karekökünü alırsak d~0~ (1 < d~0~ < √n) şeklinde bir fonksiyon elde ederiz. Eğer n sayımızın tamamen karekökü alınabiliyorsa mükemmel karedir ancak asal değildir. Aksi halde farzedelimki ilk bulduğumuz bölüm d~1~,  √n < d~1~ < n olsun. Ama n, √n’den az olan d~2~ = n / d~1~ tarafından tamamen bölünüyor. Bu nedenle tahmin yanlıştır ve eğer √n’den daha büyük bir bölen varsa o zaman çifti √n’den azdır. Böylelikle ifademiz kanıtlanmış oldu.

Son olarak kodumuzu vermeden bir iyileştirmeden daha bahsetmeliyim. Farz edelimki n tek bir sayı(2 bölen olamaz) olsun. Eğer n 2’ye kalansız bölünemiyorsa başka hiçbir çift sayıya tamamen bölünemez. İşte bu iyileştirmeden sonra değişen algoritmamız ve prosesimiz şu şekilde oluyor:

Prime.v2.cpp

/*
 * Process:  Prime Number
 * Programmer: Burak ISIKLI
 *
 */

#include<iostream.h>
#include<math.h>

bool isPrimeNumber(long int num);

int main() {
 long int number;
 cout << "Find primes: ";
 cin >> number;

 if (isPrimeNumber(number))
 cout << endl << number << ", is a prime number" << endl;
 else
 cout << endl << number << ", isn't a prime number" << endl;

 return 0;
}

bool isPrimeNumber(long int num) {
 if (number == 2)
 return true;
 if (number % 2 == 0)
 return false;
 for (long int i = 3; i <= (long int) sqrt((double) num); i++) {
 if (num % i == 0)
 return false;
 }
 return true;
}

Bu algoritmamızın iyileştirmelerden sonraki çözüm karmaşıklığı O(√n / ln(n)) oldu.

İkinci algoritma girilen sayı aralığına kadar asal sayıları listeleme. Aslında bunun için özelleşmiş spesifik bir algoritma mevcut. “Sieve Algoritması” adı verilen algoritmanın çözüm karmaşıklığı O(n^1\ /\ 2^loglogn / logn)’dir.

Sieve.cpp

/*
 * Process:  Prime Number - Sieve Algorithm
 * Programmer: Burak ISIKLI
 *
 */

#include <iostream.h>
#include <math.h>
#include <assert.h>
#include <time.h>

int main() {
 int i;
 clock_t start, stop;
 double t = 0.0;
 cout << "Find primes up to: ";
 cin >> i;

 assert((start = clock())!=-1);

 //create prime list
 int prime[i];
 int c1, c2, c3;

 //fill list with 0 - prime
 for (c1 = 2; c1 <= i; c1++) {
 prime[c1] = 0;
 }

 //set 0 and 1 as not prime
 prime[0] = 1;
 prime[1] = 1;

 //find primes then eliminate their multiples (0 = prime, 1 = composite)
 for (c2 = 2; c2 <= (int) sqrt(i) + 1; c2++) {
 if (prime[c2] == 0) {
 c1 = c2;
 for (c3 = 2 * c1; c3 <= i + 1; c3 = c3 + c1) {
 prime[c3] = 1;
 }
 }
 }

 stop = clock();
 t = stop - start;

 //print primes
 for (c1 = 0; c1 < i + 1; c1++) {
 if (prime[c1] == 0)
 cout << c1 << "\t";
 }
 cout << endl << "Run time: " << t << endl; //print time to find primes

 return 0;
}

Bu prosesimiz bize hangi sayıya kadar bulmak istediğimizi soruyor. Sayıyı girdiğimiz takdirde asal sayıları listeleyip çalışma süresini yazıyor.

Asal sayılar özellikle şifreleme(cryptography) alanında sıkça kullanılan bir konudur. Örneğin bizden 100 basamaklı asal sayı üretilmesi istense, görünüş olarak algoritmamız iyi bir zamanda sayıları kontrol edemez. İşte bu nedenle bizim algoritmamız pratikte kullanılmak amacıyla uygulanmıştır. Ancak büyük sayıların asal olup olmadığını test etmek istediğimizde olasılıksal algoritma(probabilistic algorithm) kullanılır.

Kaynaklar:

http://tr.wikipedia.org/wiki/Asal_sayı

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

http://www.dreamincode.net/code/snippet3315.htm

http://mathworld.wolfram.com/PrimeNumber.html

http://www.algolist.net/Algorithms/Number_theoretic_algorithms/Sieve_of_Eratosthenes


Comments !