Burak IŞIKLI :))

Asal Sayı(Prime Number) Algoritması:

Posted in Algorithm, C/C++ by Burak IŞIKLI on 24 Temmuz 2009

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 d0 (1 < d0 < √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 d1,  √n < d1 < n olsun. Ama n, √n’den az olan d2 = n / d1 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(n1 / 2loglogn / 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%C4%B1

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

2 Yanıt

Subscribe to comments with RSS.

  1. Mesut.Ö said, on 7 Kasım 2011 at 16:01

    Merhaba,

    Prime.v2.cpp kodunda for (long int i = 3; i < (long int) sqrt((double) num); i++) döngüsünde koşul i<= (long int) sqrt((double) num) şeklinde olması gerekmiyor mu ? Çünkü burda num = 9 seçtiğimizde < işaretinden dolayı for döngüsü çalışmıyor ve 9un asal oldugu sonucu dönüyor ?

  2. Burak IŞIKLI said, on 8 Kasım 2011 at 21:50

    Evet haklısın orada bir hata varmış.


Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Connecting to %s

%d blogcu bunu beğendi: