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 :
#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 :
#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 :
#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 :
#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 :
#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;
}
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 :
/*
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 buraya tıklayınız.
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
|
|