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

사진출처  © florianklauer, 출처 Unsplash

이 프로그램은 2019. 4. 28. 16:29에 네이버 블로그에서 작성되었습니다.

안녕하세요 tomskang입니다.

오늘은 간단하게 소수탐색 프로그램을 한번 만들습니다.

시간 복잡도는 O(Nsqrt(N))입니다.

소스코드 보겠습니다.

---

소스코드

source.cpp

#include <iostream>
#include <vector>

#define TRUE	1
#define FALSE	0

using namespace std;

int main(void) {
	vector <int> vnum; // FindPrime
	int MN; // MaxNUM
	int num, i;
	bool con = FALSE; //continue?
	double before = 0;

	cout << "MAX NUM : ";
	cin >> MN;

	if ((MN >= 2) || (MN == -1)) {
		num = 2;
		vnum.push_back(num);
		cout << "Prime_" << vnum.size() << "_:_" << num;
		cout << "____Percentage : " << (double)vnum.size() / num << endl;
	}
	for (num = 3; (num <= MN) || (MN == -1); num += 2) {
		for (i = 0; i < vnum.size(); i++) {
			if (!(num % vnum[i])) {
				con = TRUE;
				break;
			}
		}
		if (con) {
			con = FALSE;
			continue;
		}

		vnum.push_back(num);
		cout << "Prime_" << vnum.size() << "_:_" << num;
		cout << "____Percentage : " << (double)vnum.size() / num << endl;
		before = (double)vnum.size() / num;
	}

	return 0;
}

입력 : 숫자를 하나 입력

출력 : 입력한 숫자까지의 소수를 소수번호_소수_소수퍼센트순으로 모두 출력함

(-1입력하면 계속해서 찾음)

---

원리

이 프로그램에서는 소인수를 sqrt(N)까지만 찾았는데요, 그럼에도 이 프로그램은 정상작동을 합니다. 중요한 건 아니지만 이유를 적어보면

바로 sqrt(N)까지 소인수를 다 찼고 나면, 남는 수는 항상 1이거나 소수이기 때문입니다. 모든 자연수 N은 sqrt(N)보다 작은 약수 중 가장 큰 수와 sqrt(N)보다 큰 약수 중 가장 작은 수, N이 제곱수일 경우 sqrt(N)^2로 나타낼 수 있는데, 여기서 제곱수일 경우는 sqrt(N)의 내림(floor 함수)까지 계산하면 소인수 분해가 다 되니 제외하고, 왜 합성수가 아닌 N(이하 N)은 sqrt(N)보다 작은 소인수로 다 나누고 나면 소수가 남을까요?

먼저, 남은 수가 합성수라고 생각해 봅시다, 그렇다면 남은 합성수 K도 자연수이기 때문에 sqrt(K)보다 작은 수와 sqrt(K)보다 큰 수로 나누어집니다. 그리고 sqrt(K)보다 작은 수는 sqrt(N)보다 작은 수입니다.(K가 sqrt(N)에서 sqrt(N)을 넘는 N의 약수 중 가장 작은 수이기 때문에 K의 인수에서 그 인수, 또는 K/그 인수는 항상 sqrt(N)보다 작습니다.) 그런데 이미 sqrt(N)보다 작은 수는 이미 tnum의 인수가 아니기 때문에 K는 합성수일 수가 없습니다. 따라서 K가 합성수 일수가 없기 때문에 K는 항상 소수 또는 1입니다.

​

<참고 자료>

검은 그래프 - y = sqrt(N), x = sqrt(N)

빨간 그래프 - y = N/x

교점 P(sqrt(N), sqrt(N))

*빨간 그래프 위의 점 중(파란 점) x, y가 모두 sqrt(N)을 넘어가는 지점이 없다

​

이상으로 tomskang의 소수탐색프로그램 소개를 마칩니다.

---

relation content

C언어 소인수분해 프로그램 (콘솔)

(구)KMS06 : C언어 소인수분해 프로그램 + source (MSFIP)

 

C언어 분수 계산기 MSNCCL (콘솔)

KMS05 : C언어 분수 계산기 MSNCCL fraction (KMS number calculator)