15. 소수의 개수 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include<stdio.h>

int main(){
	int n;
	scanf("%d", &n);
	
	bool isPrime[n+1];
	isPrime[0] = isPrime[1] = false;
	
	for(int i = 2; i <= n; i++)
		isPrime[i] = true;
	
	for(int i = 2; i*i <= n; i++)
	{
		if(isPrime[i])
		{
			for(int j = i+i; j <= n; j = j+i)
				isPrime[j] = false;
		}
	}
	
	int count = 0;
	for(int i = 0; i < n+1; i++)
		if(isPrime[i])
			count++;
	
	printf("%d", count);
	return 0;
}

1. n까지의 소수 개수 판별법 : 에라토스테네스의 체 (시간복잡도 O(Nlog(logN)))

- 자연수 n까지의 자연수만큼의 원소를 갖는 isPrime 배열을 만든다.

- 숫자 0과 1은 소수가 아니므로 isPrime[0]과 isPrime[1]은 false로 초기화한다.

- 2부터 n까지는 true로 초기화한다.

 

핵심 내용

※ 소수인지 확인할 때 범위는 n의 제곱근까지만 확인한다.

- 예를 들어 n = 81 일때, 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 이다. 6을 중심으로 각 숫자가 짝을 이루게 된다.

따라서 제곱근인 6까지만 확인하면 나머지 숫자들도 소수가 아님을 알 수 있다.

 

에라스토테네스의 체

※ 어떤 숫자 x가 소수일 때, x의 배수는 소수가 아니므로 소수에서 제외시킬 수 있다.

 

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