C++ 소수 판별하기

 

 

 

 

---

1. 소수 판별

 

소수란 1보다 크며 1 이외의 자신으로만 나누어지는 수이다.

 

어떠한 수 n이 소수인지 판별하기 위하여 for문을 사용하여서 2부터 나누어 n-1까지의 수 중 나머지가 0이 되는 수가 존재하는 지 루프를 돌면 판별할 수 있다.

 

하지만 이러한 방식은 비효율적으로 매우 큰 수인 소수의 경우 엄청난 연산과 비교를 하는 루프를 필요로 한다.

 

그래서 이를 효율적으로 하기 위하여 특정 방법을 사용하여서 루프 횟수를 줄일 수 있다.

 

 

 

---

2. 코 드

환경 : Visual studio 2019

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool sosu(int num) {
	if (num < 2) return false;
	int a = (int) sqrt(num);
	for (int i = 2; i <= a; i++) if (num % i == 0) return false;
	return true;
}

int main() {
	vector<int> v = { 1, 2, 3, 4, 5, 13, 33, 22, 41, 91 };
	for (int i : v) {
		if (sosu(i)) {
			cout << i << " 는 소수 입니다.\n";
		}
		else {
			cout << i << " 는 소수가 아닙니다.\n";
		}
	}

	return 0;
}

 

결과

 

 

- 기존 임의의 수 n에 대하여 루프를 2부터 n번까지 반복한거의 비하여

2부터 sqrt(n) 까지의 루프만을 반복하여도 임의의 수 n이 소수인지 아닌지 판별이 가능하다.

 

 

※ sqrt 는 제곱근을 구하는 함수이다.

ex ) sqrt(4) => 2, sqrt(9) => 3

 

 

 

 

 

 

 

 

2-1. 그렇다면 왜 2 ~ sqrt(n) 만큼의 루프만 반복하여도 될까?

 

 

 

그것은 바로 제곱근의 수가 경계이기 때문이다.

 

 

 

 

예를들어 임의의 수 n = 36이 소수인지 판별한다면

 

 

 

i	a	n
2	18	36
3	12	36
4	9	36
5	-	36
6	6	36
...	...	36
12	3	36
...	...	36
35	-	36

 

i는 for문에서 사용되는 변수이며 2부터 1씩을 더하면서 루프를 반복한다.

 

 

a는 i와 곱해서 n이 되는 수 이다.

 

 

 

 

 

i는 점점 증가함에 비하여 a는 점점 감소한다.

 

 

그러면 i = 7 된 상황에서 a는 어떠한 수이겠지만 a < 6 라는 것을 확인할 수 있다.

 

 

 

 

 

이에 더하여 n = 36이 정확히 나누어지기 위해서는 자연수이여야하며 a는 6 미만의 범위를 갖으므로

 

a =  2, 3, 4, 5 

 

라는 경우의 수가 남는다.

 

 

 

 

그렇지만 이러한 경우의 수들은 이미 루프를 돌면서 i = 2, 3, 4, 5 경우 임의의 수 n이 나누어 떨어지는 지 확인하였었다.

 

 

따라서 2 ~ 제곱근까지의 정수의 범위만을 확인함으로써 임의의 수가 소수인지 판별이 가능한 것이다.