[알고리즘] 소수판별 알고리즘 C++

0.목차

• 소수의 개념
• 소수판별1 (시간복잡도 O(N) 알고리즘)
• 소수판별2 (시간복잡도 O(√N) 알고리즘)
• 소수판별3 (시간복잡도 O(Nlog(logN)) 에라토스테네스의 체 알고리즘)

---

1. 소수(Prime Number) 의 개념

소수는 1과 자기자신을 제외하고 약수를 갖지 않는 1보다 큰 자연수를 의미한다.

2는 소수다. 왜냐하면 2의 약수는 1과 자기자신인 2뿐이기 때문이다.

3은 소수다. 왜냐하면 3의 약수는 1과 자기자신인 3뿐이기 때문이다.

4는 소수가 아니다. 왜냐하면 4의 약수는 1, 2, 4 로 1과 자기자신인 4를 제외한 2가 있기때문이다.

5는 소수다. 왜냐하면 5의 약수는 1과 자기자신인 5뿐이기 때문이다.

6은 소수가 아니다. 왜냐하면 6의 약수는 1, 2, 3, 6 으로 1과 자기자신인 6를 제외한 2,3이 있기때문이다.

7은 소수다. 왜냐하면 7의 약수는 1과 자기자신인 7뿐이기 때문이다.

 

---

2. 소수판별1 (시간복잡도 O(N) 알고리즘)

이렇게 우리가 현실에서 소수를 판별하는 방법은 무엇인가? 정답은 간단하다. 2부터 해당 수-1까지 그 수와 나누어떨어지는 수가 있다면 소수가 아니고, 나누어떨어지는 수가 없으면(약수가 없으면) 소수가 된다.

이것을 코드로 옮겨보자. 입력받은 수를 N이라고 하고, 소수면 true를, 소수가 아니면 false를 return하는 함수를 만들어보면 아래와 같다.

bool isPrime1(int n) {
	for (int i = 2; i < n; i++) {
		if (n%i == 0) {//i가 n의 약수라면 소수가 아니므로 false return
			return false;
		}
	}
	//2 ~ n-1까지 약수가 없다면 소수이므로, true return
	return true;
}

위의 코드는 진짜 하나하나 모든수를 약수인지 검사를 하는 방법이다. 하지만 이보다 더 적게 걸리는 알고리즘은 없을까?

---

3. 소수판별2 (시간복잡도 O(√N) 알고리즘 )

위의 시간의 1/2제곱만큼 시간이 줄어드는 알고리즘이다. 이 알고리즘이 성립하는 이유는, 수학에서 약수를 구할때 규칙을 찾을 수 있다는 점에서 고안을 한것이다. 약수를 구할때, 해당 수의 제곱근을 중심으로 좌측에 있는 수들은 우측에있는 수와 짝을 이룬다.

말이 어려우니 예를 들어보겠다. 81의 약수는 1, 3, 9, 27, 81이 있다.

81의 제곱근은 9가된다.

9를 중심으로 좌우 짝을 찾아보면 1-81 / 3-27 / 9 가 된다. 이렇게 제곱근을 중심으로 좌-우가 짝을 이뤄 해당 수를 만들 수 있기때문에, 우리는 약수를 찾기위해서 1~9까지의 수중, 81의 약수를 구하면, 자동적으로 짝을 이루는 약수를 함께 구할 수 있다.

ex) 1은 81의 약수이다. 따라서 81/1 = 81 또한 81의 약수이다.

3은 81의 약수이다. 따라서 81/3 = 27 또한 81의 약수이다.

9는 81의 약수이다. 따라서 81/9 = 9 또한 81의 약수이다.

 

이를 이용하여 소수를 판별할때, 2~제곱근까지의 수중, 해당 수와 나누어떨어지는 수가 있는지 확인을 한 뒤, 나누어떨어지는 수가 있다면(약수가 있다면) 소수가 아니고, 없다면 소수가 된다.

 

이것을 코드로 옮겨보자. 조건은 위와 같다.

bool isPrime2(int n) {
	for (int i = 2; i <= sqrt(n); i++) {//2~n의 제곱근까지
		if (n%i == 0) {//i가 n의 약수라면 소수가 아니므로 false return
			return false;
		}
	}
	//2 ~ n-1까지 약수가 없다면 소수이므로, true return
	return true;
}

---

반응형

4. 소수판별3 (시간복잡도 O(Nlog(logN)) 에라토스테네스의 체 알고리즘)

위에 소개를 해준 1,2번 방법은 소수판별을 해야할 수가 적을때 효율적이다. N의 값이 크다고하면 2번 방법을 사용하면 효과적일것이다. 하지만 소수판별을 해야할 수가 많아지면 2번방법도 O(N√N) 의 값이 커지기 때문에, 이런 상황에선 이보다 더 효율적인 방법을 찾아야한다.

 

그 방법은 에라토스테네스의 체 알고리즘이 있다. 에라토스테네스의 체 알고리즘에서 사용한 원리는 이렇다. 

해당수가 소수라면, 해당 수의 배수들은 모두 해당수를 약수로 가지고있으므로 소수가 되지 못한다.

예를들어 2는 소수이다. 하지만 2를제외한 2의 배수인 4, 6, 8, 10, 12 ..... 들은 모두 약수로 2를 가지고있으므로, 소수가 되지 못한다.

3은 소수이다. 하지만 3을 제외한 3의 배수인 6, 9, 12, 15, 18, 21 ..... 들은 모두 약수로 3을 가지고있으므로, 소수가 되지 못한다.

말로하면 헷갈리는 부분이 있을테니, 예를들어보겠다.

 

2~50까지의 수중, 소수를 구해야한다고 해보자.

먼저 소수가 아닌 1을 제외시켜준다. 소수가 아닌수는 빨간색으로, 소수인수는 파란색으로 체크를 해주겠다.

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	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

다음수인 2를 확인해보자. 2는 소수이다. 소수이므로 파란색으로 체크를 해준뒤, 2를 제외한 2의배수들을 모두 빨간색으로 체크를 해준다.

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	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

다음수인 3을 확인해보자. 3은 소수이다. 소수이므로 파란색으로 체크해준 뒤, 3을제외한 3의 배수들을 모두 빨간색으로 체크를 해준다.

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	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

다음수인 4를 확인해보니 이미 소수가 아니라고 판별이 났으므로, 다음수인 5을 확인해보자. 5는 소수이므로 파란색으로 체크해준 뒤, 5를 제외한 5의 배수들을 모두 빨간색으로 체크해준다.

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	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

다음 수인 6도 소수가 아니라고 판별이 되었으므로, 다음수인 7을 보자. 7은 소수이므로, 파란색으로 체크해준뒤, 7을 제외한 7의 배수들을 모두 빨간색으로 체크해준다.

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	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

이런식으로 쭉 나아가며 소수판별을 해주면 결과는 아래처럼 된다.

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	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

코드로 옮기면 아래와 같다.

//n까지의 수중, 소수들을 출력하는 알고리즘
void isPrime3(int n) {
	bool *isPrime = new bool[n+1];// n까지 구해야하므로, n+1개를 동적할당
	
	//먼저 모든 배열을 true로 초기화
	for (int i = 0; i <= n; i++) {
		isPrime[i] = true;
	}


	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) {//해당수가 소수라면, 출력하고 해당수를 제외한 배수들을 모두 제외
			cout << i << " ";
			for (int j = i * 2; j <= n; j += i) {
				isPrime[j] = false;
			}
		}
	}
}