[C]백준 09.기본수학2: 4948

백준 4948

내코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int countPrime(int n) {
	int arr[250000];
	for (int i = 2; i < 2 * n + 1; i++) {
		arr[i] = i;
	}
	for (int i = 2; i < 2 * n + 1; i++) {
		if (arr[i] == 0)
			continue;
		for (int j = 2 * i; j < 2 * n + 1; j += i) {
			arr[j] = 0;
		}
	}
	int cnt = 0;
	for (int i = n + 1; i < 2 * n + 1; i++) {
		if (arr[i] != 0) {
			cnt++;
		}
	}
	return cnt;
}

int main()
{
	while (1) {
		int n;
		scanf("%d", &n);
		if (n == 0) {
			break;
		}
		printf("%d\n", countPrime(n));
	}
	
	return 0;
}

countPrime(n)함수는 에라토스테네스의 체 방식을 이용해 2*n까지 에라토스테네스의 체를 만들고 n보다 크고 2n이하인 범위의 소수의 개수를 구해주는 함수이다. 에라토스테네스의 체는 소수를 판별하는 알고리즘으로 소수들을 대량으로 빠르고 정확하게 구하는 방법이라고 한다. 소수를 판별할 범위만큼 수를 적은 뒤 2부터 시작하여 특정 수의 배수에 해당하는 수를 지우면 소수만이 남아있게 된다. 

먼저 2부터 소수인지 판별할 범위인 2n까지 배열에 인덱스값으로 배열 값을 채워준다. 그 후 2부터 2*n까지 반복하며 그 수의 배수인 인덱스의 배열값을 0으로 바꾸어준다. 그러면 인덱스 2부터 2n까지 중 소수인 인덱스의 배열값은 0이 되게 된다. 그 후 n보다 크고 2n이하인 범위의 인덱스에서 배열값이 0이 아닌 수의 개수를 세어준다면 문제를 해결할 수 있다. 배열의 크기는 2n보다 커야하기 때문에 넉넉하게 250000으로 설정하였다.

<참고 사이트: https://velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4>