Algoritma Çalışması : Asal Sayıların Hesaplanması

**Forum Kurucusu** Mesaj Sayısı : 405 Nerden : Cehennem

Bir Algoritma Hikayesi

Bu küçük yazımda asal sayılar üzerinde biraz düşünecek, hesaplanması için nasıl uygulamalar yazarız adım adım bunları gerçekleştireceğiz. Her seferinde yöntemlerimizde bir adım daha ilerleyecek ve daha hızlı sonuca ulaşan uygulamlar ortaya koyacağız. Aşağıda belirtilen yöntemler bir kaynaktan alınmış değildir, yalnızca yazarın kendi düşüncelerini ortaya koyar. Aynı konuda araştırma yapanlara temel olması, faydalanmaları amacıyla aktarılmaktadır.
Bölüm 1

Asal sayılar: Asal sayılar sadece kendine ve bire bölünen sayılardır. Bir dışında kendinden önce gelen sayılara bölünmezler.

Mantık 1 : Madem asal sayılar bir dışında kendinden önce gelen sayılara bölünmüyorlar biz de sayıyı kendinden önce gelen tüm sayılara tam bölünüp bölünmediğine bakarız. Bölünüyor ise asal değildir.

Örnek Kod 1 :

Kod:: #include <stdio.h>

int main(int argc, char *argv[])
{
printf("Sayiyi giriniz=");
int sayi;
scanf("%d",&sayi);

if(sayi<=1)
{
printf("Lutfen 1 den buyuk bir sayi giriniz!\n");
exit(1);
}

int i;
for (i=2;i<sayi;i++)
{
if(sayi%i==0)
{
printf("Sayi asal degildir.\n");
exit(1);
}
}
printf("%d sayisi bir asal sayidir.\n",sayi);

return 0;
}

Mantık 2 : Mantık 1 daima doğru sonuç verir fakat bu yöntemi daha hızlı sonuç verecek şekilde yeniden düzenlemeliyiz. Sayının 2 ye bölünmediği belli ise 2 nin katlarına da bölünmeyecektir. Yani çift sayılar kümesi={2,4,6,8,10,12 ...} içindeki sayılara da bölünmeyecektir. Denediğimiz sayıların yarısı çift sayıdır ve bunlar çıkarıldığında sayıların %50 si denenmeyecektir.

Örnek Kod 2 :

Kod:: #include <stdio.h>

int main(int argc, char *argv[])
{
printf("Sayiyi giriniz=");
int sayi;
scanf("%d",&sayi);

if(sayi<=1)
{
printf("Lutfen 1 den buyuk bir sayi giriniz!\n");
exit(1);
}

if(sayi==2)
{
printf("2 sayisi bir asal sayidir.\n");
exit(0);
}

if(sayi%2==0)
{
printf("Sayi asal degildir.\n");
exit(1);
}

int i;
for (i=3;i<sayi;i+=2)
{
if(sayi%i==0)
{
printf("Sayi asal degildir.\n");
exit(1);
}
}
printf("%d sayisi bir asal sayidir.\n",sayi);

return 0;
}

Mantık 3 : Mantık 2 bize daha hızlı sonuca ulaşmamızı sağladı. Bunu daha fazla geliştirebiliriz. şimdi 2 ve 3 ün katlarını denemeyerek daha çabuk sonuca ulaşmaya çalışalım. Bunun için nasıl bir artım yapılacağını inceleyelim.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ::Sayılar
2 3 2 X 2 X 2 3 2 X 2 X 2 3 2 X 2 X 2 3 2 X 2 X 2 3 2 X 2 X 2 3 2 X 2 ::Katları

X burada 2 ve 3 'e tam bölünmeyen sayıları işaret ediyor. Her X ifadesi arasında kaç sayı olduğunu artımlar şeklinde gösterelim ve ortak bir kalıp bulalım.

+2 +4 +2 +4 +2 +4 +2 +4 +2 +4 +2

Görülebileceği gibi 5 sayısı ile başlayarak bu sayılar 2 daha sonra 4 ile toplanarak devam ettirilir ise 2 ve 3'ün katları otomatikman atlanmış olur. x=6 olmak üzere x (x+1) (x+2) (x+3) (x+4) (x+5) sayıları içinde x (x+2) ve (x+4) 2 nin katı olduğu için, x ve (x+3) 3 ün katı olduğu için atlanıyor. Yani her 6 sayıdan 2 tanesi üzerinde deneme yapılacağı için sayıların %33 lük bölümü denenerek sonuca karar verilecektir. Eğer sıradaki asal sayıları da (5,7,11,13) düşünür iseniz işler daha çok karışacak, buna karşın elde edeceğimiz zaman kazancı gittikçe azalacaktır. Fakat kar kardır. Bazen binde 1 daha hızlı olmak bile önem arzedebilir.

Örnek Kod 3:

Kod:: #include <stdio.h>

int i;

//Bu fonksiyon sıradaki sayının
//bulunması işlemini gerçekleştiriyor.
void ver()
{
static int s=0;
if(s==0)
{
i+=2;
s=1;
}
else
{
i+=4;
s=0;
}
}

int main(int argc, char *argv[])
{
printf("Sayiyi giriniz=");
int sayi;
scanf("%d",&sayi);

if(sayi<=1)
{
printf("Lutfen 1 den buyuk bir sayi giriniz!\n");
exit(1);
}

if(sayi<4)
{
printf("%d sayisi bir asal sayidir.\n",sayi);
exit(0);
}

if( sayi%2==0 || sayi%3==0 )
{
printf("Sayi asal degildir.\n");
exit(1);
}

for (i=5;i<sayi;ver())
{
if(sayi%i==0)
{
printf("Sayi asal degildir.\n");
exit(1);
}
}
printf("%d sayisi bir asal sayidir.\n",sayi);

return 0;
}

Mantık 4 : Elimizde bir sayı olsun. Örneğin 101 (bir asal sayıdır). Eğer 2 ye bölünmediği belli ise, bu başka bir anlama daha gelir. 101/2 ile 101 arasındaki sayılara da bölünmeyeceği anlamına gelir. Çünkü 101 sayısının biraz önce bahsettiğimiz aralıktaki sayılara bölümü 1 ile 2 aralığındaki reel sayılara denk gelir. 101 sayısının bir sayıya bölünmesi demek bölen ile bölümün tamsayı olması demektir. 1 ile 2 arasındaki sayılar tamsayı olmadığı için 101/2 ile 101 arasındaki sayılar 101 için bir tamsayı çarpan olamazlar. Bu anlattığım bilgiler ışığında 3 sayısı da çarpan olarak kontrol edildiğinden, düşünüldüğünde 101/3 e kadarki sayıların denenmesi yeterli olmalıdır. Sıradaki sayı olan 4 sayısı 2 nin katı olduğu için bu sayı da dahil edilebilir. Uygulamamızı buna göre yazacağız. Bu yöntem ile sayıların (1/4)*(1/3)=1/12=%8.3 lük bir kısmı denenerek sayının asal olup olmadığına karar verilmektedir.

Örnek kod 4 :

Kod:: #include <stdio.h>

int i;

void ver()
{
static int s=0;
if(s==0)
{
i+=2;
s=1;
}
else
{
i+=4;
s=0;
}
}

int main(int argc, char *argv[])
{
printf("Sayiyi giriniz=");
int sayi;
scanf("%d",&sayi);

if(sayi<=1)
{
printf("Lutfen 1 den buyuk bir sayi giriniz!\n");
exit(1);
}

if(sayi<4)
{
printf("%d sayisi bir asal sayidir.\n",sayi);
exit(0);
}

if( sayi%2==0 || sayi%3==0 )
{
printf("Sayi asal degildir.\n");
exit(1);
}

int limit=sayi/4+1;
for (i=5;i<limit;ver())
{
if(sayi%i==0)
{
printf("Sayi asal degildir.\n");
exit(1);
}
}
printf("%d sayisi bir asal sayidir.\n",sayi);

return 0;
}

Mantık 5 : Sayımız 81 olsa idi, biraz düşünelim. Biliyoruz ki 9*9=81 ediyor. Asal sayı değil ama bize önemli bir ayrıntıyı işaret ediyor. Diyor ki: 81 sayısı olarak 3 ve 9'a bölünürüm. Bu sayılar beni ele verir. Fakat bu sayılara bölünmemiş olsam bile 9 dan sonraki sayıları beni bölmekte kullanmayın. Çünkü o sayıları zaten denediniz, diyor bize. Nasıl yani? şöyle: "81 sayısı asal mıdır?" sorusunun cevabını ararken kök(81) e kadarki sayılar ile inceleme yapmamız yeterli olacaktır. 9 dan sonraki sayılar ile deneme yapsak, 81/10=8.1 81/11=7.36 gibi sonuçlar 9 dan küçük olmaktadır. Eğer sayının içinde bir tamsayı çarpan olsa idi bunları zaten 9'a kadarki sayıların denenmesi ile bulmalı idik. 81 sayısı asal mıdır sorusunun cevabı: 9 a kadarki sayılara bölünmüyor ise asaldır olacaktır. Bu yöntem ile sayıların ( kok(n) / n )*(1/3)*100=%( 33 / kok(n) ) kadarlık bölümü denenir. Bu n=2500 için % 0.66, n=86000 için % 0.11 oranında deneme demektir. n=10000000 için sadece 1055 deneme yapılmaktadır.

Örnek kod 5:

Kod:: #include <stdio.h>
#include <math.h>

int i;

void ver()
{
static int s=0;
if(s==0)
{
i+=2;
s=1;
}
else
{
i+=4;
s=0;
}
}

int main(int argc, char *argv[])
{
printf("Sayiyi giriniz=");
int sayi,kok;
scanf("%d",&sayi);

if(sayi<=1)
{
printf("Lutfen 1 den buyuk bir sayi giriniz!\n");
exit(1);
}

if(sayi<4)
{
printf("%d sayisi bir asal sayidir.\n",sayi);
exit(0);
}

if( sayi%2==0 || sayi%3==0 )
{
printf("Sayi asal degildir.\n");
exit(1);
}

kok=sqrt(sayi)+1;
for (i=5;i<kok;ver())
{
if(sayi%i==0)
{
printf("Sayi asal degildir.\n");
exit(1);
}
}
printf("%d sayisi bir asal sayidir.\n",sayi);

return 0;
}

**Forum Kurucusu** Mesaj Sayısı : 405 Nerden : Cehennem

Mantık 6 : şu ana kadar 2 ve 3 için hangi sayıları denemeyeceğimizi kesin olarak ortaya koyduk. Fakat 5,7,11,13,17 ... için? Bunu sonsuza kadar yapamayız. En ideal inceleme sayının kareköküne kadar yapılmalıdır..... En ideal inceleme sayının kareköküne kadarki asal sayılar ile yapılmalı! Fakat bir sonuca varmak için sayının kareköküne kadarki asal sayıları hesaplamak hız açısından ne kadar ekonomik olur bunu bilemiyorum. Fakat bir yerlerde başka bir hesaplamadan kalan asal sayılarımız olsa idi pratik bir yaklaşım olurdu. Bu yöntemin bu şekilde uygulamaya dökülmesi bir önceki yöntemden daha hızlı olacagı kesin değildir. Bu nedenle yöntemi program koduna dökmeden 7 numaralı mantığa geçiyorum.

Mantık 7 : Eğer n'e kadar tüm asal sayıları hesaplayan bir program yazsak önceden bir diziye atmış olduğumuz asal sayılar sonraki sayının denetlenmesinde işimize yarayacaktır. Yeni asal sayılar bulundukça ileride kullanmak amacıyla bir diziye kayıt edilebilir. Bu düşüncemizde yukarıdaki düşüncelerimizi birleştireceğiz.
1) Sayının kareköküne kadar denetleme yapacağız.
2) 2,3,5 sayıları ve katları için deneme yapılmayıp bu sayılar atlanacak.
3) Denetleme sırasında elde ettiğimiz asal sayıları bir diziye kaydedecek ve sonraki sayılar için kullanacağız. Böylece sadece asal sayılar ile bölme denemesi yapılacagı için bundan önceki programlarımızdan çok daha hızlı sonuca ulaşacaktır.

Örnek kod 7 :

Kod:: /*
Asallar v0.07 Girilen sayıya kadar olan asal sayıları bulur.
Copyright (C) 2004 Engin KUZU

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/

//http://www.gnu.org/copyleft/gpl.html
//Turkce cevirisi: http://www.belgeler.org/howto/gpl_copy.html

#include <stdio.h>
#include <math.h>

// 2,3,5 iptal edildi. Sorgulama dizilimi 7 den baslayarak,
// +4 +2 +4 +2 +4 +6 +2 +6
// seklinde olacak.
// 2,3,5,7 hazir yazilacak.

int ver ( int s )
{
static int i=-1;
i++;
if(i==8)
i=0;
switch(i)
{
case 0: s+=4; break;
case 1: s+=2; break;
case 2: s+=4; break;
case 3: s+=2; break;
case 4: s+=4; break;
case 5: s+=6; break;
case 6: s+=2; break;
case 7: s+=6; break;
}
return s;
}

int main(int argc, char *argv[])
{
unsigned int dizi[1000000];
dizi[0]=2; dizi[1]=3; dizi[2]=5; dizi[3]=7;
unsigned int sayac=3,sayi,i,temp;
system("clear");

do{
printf("Kaca kadarki asal sayilari istiyorsunuz=");
scanf("%d",&sayi);

if(sayi<8)
{
system("clear");
printf("8 den kucuk bir sayi girmeyiniz\n");
i=0;
}
else { i=1; }
}while(i==0);

printf("Asal sayilar=2,3,5,7");
int son=7,karekok,durum;
karekok=sqrt(sayi);

while(1)
{
son=ver(son);
if(sayi<son)
{
printf("#\n%d tane bulundu.\n",sayac+1);
exit(0);
}
durum=0;
for(i=0;dizi[i]<=karekok && i<sayac;i++)
{
temp=dizi[i];
if( son%temp == 0 )
{
durum=1;
break;
}
}

if(durum==0)
{
printf(",%d",son);
sayac++;
dizi[sayac]=son;
}
}
}

Yukarıdaki uygulama GPL lisansı altındadır. Özgür yazılımdır. Lisansın gösterdiği şekilde istifade edebilirsiniz.

Yukarıdaki uygulamalar linux ortamında rahat bir şekilde derlenebilir. math.h başlık dosyası kullanılan dosyaları derlerken -lm parametresini unutmayınız. Örnek: cc kod.c -o kod -lm Yukarıda geçen program örneklerine ve derlenmiş hallerine ulaşmak için

http://www.enginkuzu.org/indir/asal.tar.gz

Bölüm 2

Yakında burada daha hızlı olmasa da yeni bir yöntem üzerinde düşüneceğiz.

Telif Hakkı © 2005 Engin KUZU Yayın tarihi : 4 Mart 2005
Güncelleme (Bölüm 2) : 2 Haziran 2006
Dökümanın orjinal adresi : http://www.enginkuzu.org/asal-sayilar.php

Emeğine Sağlık Engin Kuzu