KMS04 : C++ 소수탐색 프로그램 Ver3 (source)

 

사진출처 © florianklauer, 출처 Unsplash

안녕하세요 tomskang입니다. 오늘은 지난번에 만든 소수 탐색기를 업그레이드 시켜보았는데요

이번에 확실하게 프로그래밍을 각잡고 해서, 최적화되었다 할 수는 없지만, 여러 방면으로 지금까지 나온 소수탐색기 중 가장 혁신적인 성능을 가졌습니다.

 

<지난번 코드>https://blog.naver.com/tomskang/221714771632

[C++]소수탐색 프로그램 Ver2(source)

<목차>

1.    바뀐점
2.       소스
3. 함수설명
4.       실행

 

바뀐점은 위와 같습니다. 대부분의 블로그에서는 보지 못했던 새로운 기능을 추가하고자 생각하였고, 그 결과 "저장"이라는 새로운 기능이 생겨났습니다.

---

[소스]

(425line)

#include <iostream>
#include <algorithm>
#include <vector>
#include <windows.h>
#include <ctime>

using namespace std;

enum { standard, list };

typedef long long pd;

#define TRUE	1
#define FALSE	0

#define FILE_READ_N		500000 //한번에 .bin에서 소수 데이터를 읽는 양
#define PRINT_PRIME		500 //소수 PRINT_PRIME개당 하나를 출력
#define FILE_WRITE_N	2 * PRINT_PRIME //한번에 .bin에 소수 데이터를 쓰는 양
#define TEST_NUM		10000 //소수 TEST_NUM개당 1개씩 소수인지 검사함

#define LINE_PER_PRIME	8 // decode시 한 줄당 출력하는 소수의 수 (must : mode = stndard)

#define MODE			standard // DECODE 출력모드[standard/list]

#define MAX(x, y)	(((x) > (y)) ? (x) : (y))
#define MIN(x, y)	(((x) < (y)) ? (x) : (y))

bool C;

enum { BLACK = 0, BLUE, GREEN, CYAN, RED, MAGENTA, BROWN, LIGHTGRAY, DARKGRAY, LIGHTBLUE, LIGHTGREEN, LIGHTCYAN, LIGHTRED, PINK, YELLOW, WHITE };

inline void textcolor(int text, int back) {
	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), text | (back << 4));
}
// void textcolor(alpa, beta) 출처| https://andrew0409.tistory.com/162

//ab
pd f(pd N) {
	if (C) {
		N += 2;
		C = FALSE;
	}
	else {
		N += 4;
		C = TRUE;
	}
	return N;
}

void delay(double sec) {
	clock_t ct;
	ct = clock();
	while (ct + CLK_TCK * sec > clock());
}

bool ISPRIME(pd N) {
	for (pd i = 2; i < sqrtl((long double)N); i++) {
		if (!fmodl(N, i))
			return FALSE;
	}
	return TRUE;
}

int SETUP(void);
int KMS04main(void);
int FtoT(void); // F(.bin) to Text
void KMS04refresh(void);

int main(void) {
	char c;
	system("color 0f");
	do {
		cout << "KMS05 type? " << endl;
		cout << "[SETUP | S]  " << "[KMS05 | KorM]  " << "[DECODE TO TEXT | D]  " << endl << endl;
		textcolor(LIGHTCYAN, BLACK);
		cout << "-> ";
		cin >> c;
		if (('a' <= c) && (c <= 'z'))
			c += 'A' - 'a';

		switch (c) {
		case 'S':
			return SETUP();
			break;
		case 'K':
		case 'M':
			return KMS04main();
			break;
		case 'D':
			return FtoT();
			break;
		}

	} while (TRUE);

	return 0;
}

// setup main
int SETUP(void) {
	// ********** setup ********** //
	FILE* fp;
	pd arr[3] = { 2, 3, 5 };
	long size;
	char c;

	system("cls");

	fopen_s(&fp, "pdata.bin", "rb");
	if (fp != NULL) {
		fseek(fp, 0, SEEK_END);
		size = ftell(fp);
		fclose(fp);


		if (size > 20) {
			cout << size << " data will disappear" << endl;
			cout << "Is it okay ? " << endl << endl;

			cout << "[YES | Y]  [NO | N]" << endl << "-> ";
			cin >> c;

			if ((c == 'N') || (c == 'n'))
				return 0;
		}
	}

	system("cls");
	delay(0.5);
	fopen_s(&fp, "pdata.bin", "wb");
	if (fp == NULL) {
		cout << "file(pdata.bin) open(wb) error" << endl;
		return 0;
	}
	fwrite((void*)arr, sizeof(pd), 3, fp);
	cout << "setup seccess" << endl;
	return 0;
}

void KMS04refresh(void) {
	vector<pd> prime;
	pd num = 0;
	bool con = FALSE;

	FILE* fpr;
	FILE* wpr;
	pd* file_arr = new pd[MAX(FILE_READ_N + 1, FILE_WRITE_N + 1)];
	int readCnt1;
	int readCnt2;
	long long K;

	textcolor(BLACK, WHITE);

	// ********** reading file ********** //

	fopen_s(&fpr, "ppdata.bin", "rb");
	if (fpr == 0) {
		cout << "file(pdata.bin) open(rb) error" << endl;
		return;
	}

	for (int forcnt = 0; TRUE; ) {
		readCnt1 = fread((void*)file_arr, sizeof(pd), FILE_READ_N, fpr);
		if (readCnt1 < FILE_READ_N) {
			if (feof(fpr) != 0) {
				for (int i = 0; i < readCnt1; i++) {
					if (file_arr[i] <= 1)
						continue;
					prime.push_back(file_arr[i]);
				}

				delay(1);
				system("cls");
				cout << "file read success" << endl;
				cout << "starting KMS05..." << endl;
				delay(1.5);
				system("cls");
				delay(0.5);

			}
			else {
				cout << "file read failed" << endl;
				return;
			}
			break;
		}
		for (int i = 0; i < FILE_READ_N + 1; i++) {
			if (file_arr[i] <= 1)
				continue;
			prime.push_back(file_arr[i]);
		}
		forcnt++;
		if (!(forcnt % 10))
			cout << "read " << forcnt * FILE_READ_N << "elements" << endl;
	}

	fclose(fpr);
	fopen_s(&wpr, "pdata.bin", "wb");
	K = prime.size();
	readCnt1 = 0;
	for (int i = 0; i < K; i++) {
		file_arr[readCnt1++] = prime[i];
		if (readCnt1 >= FILE_WRITE_N) {
			fwrite((void*)file_arr, sizeof(pd), FILE_WRITE_N, wpr);
			readCnt1 = 0;
		}
	}

	fclose(wpr);
	return;
}

//main part
int KMS04main(void) {
	vector<pd> prime;
	pd num;
	bool isPrime = TRUE;
	long file_size;

	FILE* fpr;
	pd* file_arr = new pd[MAX(FILE_READ_N + 1, FILE_WRITE_N + 1)];
	int readCnt1, readCnt2;

	textcolor(GREEN, BLACK);
	system("cls");

	// ********** reading file ********** //

	fopen_s(&fpr, "pdata.bin", "rb");
	if (fpr == 0) {
		cout << "file(pdata.bin) open(rb) error" << endl;
		return 0;
	}

	// get .bin's file size
	fseek(fpr, 0, SEEK_END);
	file_size = ftell(fpr) / sizeof(pd);
	fseek(fpr, 0, SEEK_SET);

	cout << "if pdata.bin file was too big, percent indicator won't working" << endl;
	for (int forcnt = 0; TRUE; ) {
		readCnt1 = fread((void*)file_arr, sizeof(pd), FILE_READ_N, fpr);
		if (readCnt1 < FILE_READ_N) {
			if (feof(fpr) != 0) { for (int i = 0; i < readCnt1; i++) { prime.push_back(file_arr[i]); } }

			delay(1);
			system("cls");
			cout << "file read success" << endl;
			cout << "starting KMS05..." << endl;
			delay(1.5);
			system("cls");
			delay(0.5);
			break;
		}
		for (int i = 0; i < FILE_READ_N + 1; i++) {
			if (file_arr[i] <= 1)
				continue;
			prime.push_back(file_arr[i]);
		}
		forcnt++;
		if (!(forcnt % 10)) {
			cout << "read " << forcnt * FILE_READ_N << "elements\t" << (long)(prime.size() * 100 / file_size) << "percent complete" << endl;
		}
	
	}
	fclose(fpr);

	// ********** cuclulating ********** //

	fopen_s(&fpr, "pdata.bin", "ab");
	textcolor(WHITE, BLACK);
	if (fpr == 0) {
		cout << "file(pdata.bin) open(ab) error. maybe file doesn't exist" << endl;
		return 0;
	}

	readCnt1 = 0; // valueable for fwrite
	readCnt2 = 4; // valueable for print, test

	C = (fmodl(prime.at(prime.size() - 1), 6.0) == 1) ? FALSE : TRUE;
	for (num = f(prime.at((int)prime.size() - 1)); TRUE; num = f(num)) {
		for (int i = 2; ((sqrtl(num)) >= prime[i]); i++) {
			if (!(fmodl(num, prime[i]))) {
				isPrime = FALSE;
				break;
			}
		}

		if (!isPrime) { // is num isn't prime -> continue
			isPrime = TRUE;
			continue;
		}

		prime.push_back(num);
		if (readCnt2 >= PRINT_PRIME) {
			cout << prime.size() << "th prime : " << num;
			cout << "        " << num / 1000 << "K" << "\t" << num / 1000000 << "M" << endl; // print prime
			readCnt2 = 0;
		}

		file_arr[readCnt1++] = num;
		readCnt2++;

		if (!(prime.size() % TEST_NUM)) {
			if (ISPRIME(num)) {
				textcolor(GREEN, BLACK);
				cout << "[EXAMINATION : seccessful]" << endl;
				textcolor(WHITE, BLACK);
			}
			else {
				textcolor(LIGHTRED, WHITE);
				cout << "ERROR : founded prime was not prime" << endl;
				cout << "close KMS04" << endl;
				cout << "[This programm Recommend setup this program]" << endl << endl;
				textcolor(WHITE, BLACK);
				system("pause");
				break;
			}
		}
		if (readCnt1 >= FILE_WRITE_N) {
			fwrite((void*)file_arr, sizeof(pd), FILE_WRITE_N, fpr);
			readCnt1 = 0;
		}
	}

	fclose(fpr);
	delay(1);
	system("cls");
	cout << "KMS04 closing..." << endl;
	delay(2);
	system("cls");

	return 0;
}

#define FILE_NUM	100000000 //끊는 단위 [10^N이여야 함]
#define FILE_N_READ	"억" //FILE_NUM 읽는 법

int FtoT(void) {
	FILE* BIN;
	FILE* TXT;

	pd arr[6];
	int readCnt;

	//char TXTname[50] = { NULL, };

	int count = 0;
	int fnameCnt = 0;

	const char* ending = "\n \n MADE BY TOMSKANG | KMS04 \n COPYRIGHT TO TOMSKANG \n KMS04- SEARCHING PRIME V^";
	char file_name[40];

	system("cls");
	textcolor(YELLOW, BLACK);

	// ********** file open ********** //

	fopen_s(&BIN, "pdata.bin", "rb");
	sprintf_s(file_name, 40, "Decode 0-1%s.txt", FILE_N_READ);
	fopen_s(&TXT, file_name, "wt");
	if ((BIN == NULL) || (TXT == NULL)) {
		cout << "file open failed ! " << endl << endl;
	}

	// ********** standard file output ********** //

	while (TRUE) {
		readCnt = fread((void*)arr, sizeof(pd), 5, BIN);

		if (readCnt < 5) {
			if (feof(BIN) != 0) {
				for (int i = 0; i < readCnt; i++) {
					if (arr[i] <= 1)
						continue;

					if (count == LINE_PER_PRIME) {
						if (MODE == standard) { fprintf(TXT, "\n"); }
						count = 0;
					}

					fprintf(TXT, "%.0lf %c", (long double)arr[i], (MODE == standard) ? '\t' : ' ');
					count++;
				}
			}
			else
				cout << "decode fail!" << endl;
			fprintf(TXT, "%s", ending);
			cout << "fin" << endl;
			break;
		}
		else {
			for (int i = 0; i < 5; i++) {

				if ((long double)arr[i] > (long double)FILE_NUM* (fnameCnt + 1)) {
					cout << fnameCnt + 1 << "th file fin" << endl;
					fprintf(TXT, "%s", ending);
					fclose(TXT);
					++fnameCnt;
					sprintf_s(file_name, 40, "Decode %d%s-%d%s.txt", fnameCnt, FILE_N_READ, fnameCnt + 1, FILE_N_READ);
					fopen_s(&TXT, file_name, "wt");
					count = 0;
				}

				if (arr[i] <= 1)
					continue;

				if (count == LINE_PER_PRIME) {
					if (MODE == standard) { fprintf(TXT, "\n"); }
					count = 0;
				} //*/
				fprintf(TXT, "%.0lf %c", (long double)arr[i], (MODE == standard) ? '\t' : ' ');
				count++;

			}
		}
	}

	fclose(BIN);
	fclose(TXT);

	cout << "decode success" << endl;
	cout << "MADE BY TOMSKANG" << endl;
	return 0;
}

---

[함수설명]

int SETUP(void);

말그대로 SETUP를 하는 함수입니다. 이미 파일에 데이터가 있을때, 'N'을 입력하면 SETUP을 하지 않습니다.

int KMS04main(void);

소수탐색을 하는 함수입니다. 이 함수의 시간복잡도를 이 프로그램의 시간복잡도로 적었습니다.

int FtoT(void); // F(.bin) to Text

디코딩을 하는 함수입니다. 프로그램을 런 하기 전 #define을 이용해 standard모드로 출력할지 list모드로 출력할지 정할 수 있습니다.

---

​[실행]

KMS04.exe

Decode.txt

이상으로 KMS04(소수탐색 프로그램2.5)를 마칩니다.

---

relation content

C언어 소수탐색 프로그램 Ver2

 

C언어 소수탐색 프로그램 Ver1

KMS04 : C언어 소수탐색 프로그램 Ver1 (source)