#include <iostream>
#include <array>
#include <vector>
#include <cmath>
#include <fstream>
using namespace std;
const int bt[8] = {128, 64, 32, 16, 8, 4, 2, 1 };
const int blokSIZE = 131072; // 131072 adet char içine 1.048.576 adet bit konur.
const int bs8 = blokSIZE * 8;
unsigned long long x, bulunanAsal = 2;
unsigned long long kacMilyon;
int yanit = 0;
bool yaz = false;
clock_t enbas, bitis, tamponZaman, tmp;
float vecOpenSN = 0, ayiklaSn = 0;
float sureSn = 0;
const int SNtoMS = 1000000; // clock() 'u <> saniye katsayısı ( Linux da 1.000.000' a böl, windowsda 1.000'e böl)
class BirMilyonBit { //1.048.576 bit
public:
BirMilyonBit ( unsigned char doldur = 255 ) {
for ( unsigned int i = 0; i < blokSIZE; i++ ) {
blok[i] = doldur;
}
}
array<unsigned char, blokSIZE> blok;
};
class SayilarVectoru {
public:
BirMilyonBit hepsiBir;
unsigned char * p;
unsigned long long kacMilyon;
vector<BirMilyonBit>bloklar;
SayilarVectoru ( unsigned long long kac ) {
kacMilyon = kac / ( blokSIZE * 16 );
if ( kac % blokSIZE > 0 ) kacMilyon += 1;
for ( ulong x = 0; x < ( kacMilyon ); x++ ) {
bloklar.push_back ( hepsiBir );
}
bloklar.shrink_to_fit();
}
~SayilarVectoru() {
bloklar.clear();
bloklar.shrink_to_fit();
}
// toplam vectörün içinde en baştan kaçıncı bitin değerini öğrenmek istersiniz
bool getB ( const unsigned long long &x ) {
return 0 != ( bt[x % 8] & int ( bloklar[x / bs8].blok[ ( x % bs8 ) / 8] ) );
}
// toplam vectörün içinde en baştan kaçıncı bitin değerini 0 yapacaksını
void setB0 ( const unsigned long long &x ) {
p = &bloklar[x / bs8].blok[ ( x % bs8 ) / 8] ;
*p = ( ~ ( bt[x % 8] ) & int ( *p ) );
}
};
string binle ( long long k, string symbol = "," ) {
int artik;
string s = to_string ( k );
if ( k > 999 ) {
artik = s.length() % 3;
if ( artik == 0 ) {
artik = 3;
}
for ( int i = artik; i < int ( s.length() ); i = i + 4 ) {
s.insert ( i, symbol );
}
}
return s;
}
float SN ( clock_t &bas, clock_t &son ) {
return float ( son - bas ) / SNtoMS;
}
int main() {
unsigned long long kac = 1048576;
// Programın çalışacağı aralık ve çıktı yazılıp yazılmayacağı giriliyor
cout << "YeniAsal(OOP))PROGRAMI \nKaça kadar? " << endl;
kac = 1000000000; //bu satır hızlıca test etmek için konmuştur. 1milyara kadar asalları hesap eder
//bunu kapatıp alttakini açarsanız istediğiniz sayıya kadar hesap eder.
//cin >> kac; //üst satırı commentleyip bunu açarsanız kaça kadar hesap edeceğini sorar.
cout << "\n çıktı istiyormusun ? (1=istiyorum , başka sayı=istemiyorum)" << endl;
//cin >> yanit; //test için commentlendi, bunu açıp alt satırı commentlerseniz çıktı isteyip istemediğinizi sorar.
yanit = 2;
if ( yanit == 1 ) yaz = true;
cout << "1 ile " << binle ( kac, "," ) << " arasındaki Asal sayıları arayacağım" << endl;
// sayıların asallığını temsil eden başlangıç vectörünü oluştur.Bütün bitlere 1 yazar..
//sayılar'ı ayarla ******kac ve kacmilyon değişkenleri atanınca bu kısmı çalıştıracağız.
enbas = clock();
tamponZaman = clock();
SayilarVectoru sayilar ( kac );
bitis = clock();
vecOpenSN = SN ( tamponZaman, bitis );
// hesMax: kaç ın karekökünden büyük sayı kaç'ı tam bölemez. Sadece tek sayıları aldığımız için yarısını alıyoruz.
unsigned long hesMax = int ( sqrt ( kac ) / 2 ) + 1;
// sy katlarını silaceğimiz sayı
unsigned long sy;
tamponZaman = clock();
// A S A L S A Y I L A R H E S A P L A N I Y O R
/*
sy katlarını sileceğimiz sayıyı veriyor 2,3,5,7,9,11,13,15,17,19... gibi
önce sy'nin hali hazırda sıfırı olduğunu kontrol etmeliyiz.Bunun için
sy'nin durumunu hangi byte'ın hangi bitinden okuyacağımızı hesaplamalıyız.
sayılar:2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,
y-> :0,1,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,
ch : 0,0,0,0,0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
chBit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
*/
//3'ün katları için özel bölüm
sy = 3; //katlarını sileceğimiz sayı
// burada x inci biti sıfırla
for ( unsigned long long x = 4; x <= kac / 2 + 1; x += 3 ) {
sayilar.setB0 ( x );
}
//sonraki sayılar toplu işlem
unsigned long long kacar;
unsigned long long y;
for ( x = 2; x <= hesMax; x++ ) { //x tek sayıları sakladığımızı var saydığımız uzayda kaçıncı tek sayı olduğunu temsil ediyor.
sy = 2 * x + 1; //katlarını sileceğimiz sayı
if ( sayilar.getB ( x ) ) {
kacar = 3 * sy; //3'ün katlarını sıfırlamayacağız, 3'e özel önceki satırlarda 3'ün katları sıfırlandı zaten
for ( y = x; y <= kac / 2 + 1 - kacar; y += kacar ) { //y:sayiya karşılık gelen bit.
sayilar.setB0 ( y + 2*sy );
sayilar.setB0 ( y + 3*sy );
}
if ( ( y + 2 * sy ) <= kac / 2 + 1 ) {
sayilar.setB0 ( y + 2 * sy );
}
}
}
bitis = clock();
sureSn = SN ( tamponZaman, bitis );
//a s a l s a y ı l a r ı a y ı k l a
tamponZaman = clock();
hesMax = kac / 2;
unsigned long long sonAsalSayi = 0;
string dosyaAdi = "asalSayilar.txt";
fstream dosya;
unsigned long long i;
dosya.open ( dosyaAdi, ios::out | ios::trunc );
if ( dosya.is_open() ) {
dosya << "1 ile " << binle ( kac, "," ) << " arasındaki Asal sayılar:" << endl;
if ( yaz ) {
dosya << "2 ";
dosya << "3 ";
for ( i = 2; i < hesMax; i++ ) {
if ( sayilar.getB ( i ) ) {
dosya << 2 * i + 1 << " ";
bulunanAsal++;
}
}
} else {
for ( i = 2; i < hesMax; i++ ) {
if ( sayilar.getB ( i ) ) {
bulunanAsal++;
}
}
dosya << "kullanıcı asal sayıları yazdırmamayı tercih etti";
}
for ( i = hesMax; i > 2; i-- ) {
if ( sayilar.getB ( i ) ) {
sonAsalSayi = 2 * i + 1;
break;
}
}
bitis = clock();
ayiklaSn = SN ( tamponZaman, bitis );
dosya << "\n\n1 ile " << binle ( kac, "," ) << " arasında. " << binle ( bulunanAsal, "," ) << " tane asal sayı buldum" << endl;
dosya << endl << "bulunan en son asal sayı: " << binle ( sonAsalSayi, "," ) << endl;
dosya << "\nHesaplama zamanları özeti:\n";
dosya << sayilar.kacMilyon << " elemanlı vektör aç : " << vecOpenSN << "sn.\n";
dosya << "Asal sayıların hesaplanması : " << sureSn << "sn.\n";
dosya << "Asal ayıklama + dosyalara yazılması: " << ayiklaSn << "sn.\n";
dosya << "toplam geçen süre : " << SN ( enbas, bitis ) << "sn.\n";
}
dosya.close();
cout << "\n1 ile " << binle ( kac, "," ) << " arasında. " << binle ( bulunanAsal, "," ) << " tane asal sayı buldum," << endl;
if ( yaz )
cout << " Bulunan Asal sayı listesini \"asalSayilar.txt\" dosyasına kaydettim." << endl;
else
cout << " Bulunan Asal sayı hesap özetini \"asalSayilar.txt\" dosyasına kaydettim." << endl;
cout << endl << "bulunan en son asal sayı: " << binle ( sonAsalSayi, "," ) << endl;
cout << "\nHesaplama zamanları özeti:\n";
cout << sayilar.kacMilyon << " elemanlı vektör aç : " << vecOpenSN << "sn.\n";
cout << "Asal sayıların hesaplanması : " << sureSn << "sn.\n";
cout << "Asal ayıklama + dosyalara yazılması: " << ayiklaSn << "sn.\n";
cout << "toplam geçen süre : " << SN ( enbas, bitis ) << "sn.\n";
}
amatörüm, kusur hata varsa affola…
release modunda derlerseniz, benim bilgisayarda 2.5sn civarında 1 ile 1milyar arasındaki sayıların içindeki asalları buluyor.
hızlı modda derlemek için aşağıdaki şu şekilde derleyebilirsiniz:
g++ main.cpp -o cpp.run -Ofast
- ve 90. satırları comment yapıp, 87. ve 89. satırların kommentini açınca:
kaça kadar sayıların arasından asalları bulmak istediğinizi size sorar ve çıktı istiyormusun sorusuna 1 girerseniz, asal sayıların listesini bulunduğu dizene txt dosyasına yazar.
