BOJ 4913 : 페르마의 크리스마스 정리

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/4913

 

 

1,000,000의 크기의 수를 매번 소수 판단할 수 없으므로 에라토스테네스의 체를 이용하여 메모해둔다.

그리고 매번 L과 U에 포함된 소수의 개수와 소수 중 제곱수의 수를 셀 수 없으므로 아래와 같이 메모한다.

 

#define MAX (1000000)

int L, U;
int prime[MAX + 100];
int primeSum[MAX + 100];
int squreSum[MAX + 100];

int main()
{
	makePrime(); /* 에라토스테네스의 체 */

	squreSum[2] = primeSum[2] = 1;

	for (int i = 3; i <= MAX;i++)
	{
		if (!prime[i]) primeSum[i] = primeSum[i - 1] + 1;
		else primeSum[i] = primeSum[i - 1];

		if (!prime[i] && (i % 4) == 1) squreSum[i] = squreSum[i - 1] + 1;
		else squreSum[i] = squreSum[i - 1];
	}
    
    ...
    
}

 

primeSum[i] = i 까지 소수의 합

squreSum[i] = i 까지 소수 중 제곱수의 합으로 나타낼 수 있는 수의 합

 

위와 같이 정의하면,

primeSum[U] - primeSum[L - 1] = [1 ~ U] 까지의 소수의 합 - [1 ~ L - 1]까지 소수의 합 = [L, U] 소수의 합

으로 O(1)만에 계산이 가능하다.

 

이 방법도 memoization 기법이며, 다이나믹 프로그래밍에 많이 쓰인다.

 

2는 소수고, 또한 1²+1²로 나타낼 수 있으므로 squreSum[2] = primeSum[2] = 1로 초기화 한다.

 

마지막으로 경우를 3개로 나누어서 출력한다.

 

1) L >= 1 : L이 자연수인 경우 (U는 항상 L보다 크다)

2) L이 음수이고, U는 양수인 경우

3) 둘 다 음수인 경우.

 

음수는 소수가 아니고, 제곱수로도 표현할 수 없으므로, 

 

2) L ~ U의 합은 0 ~ U와 동일하다.

3) 둘 다 0을 출력한다.

 

최종 코드를 참고하자.

#include <stdio.h>

#define MAX (1000000)

int L, U;
int prime[MAX + 100];
int primeSum[MAX + 100];
int squreSum[MAX + 100];

void makePrime()
{
	prime[1] = 1;
	for (int i = 2; i * i <= MAX; i++)
	{
		if (!prime[i])
		{
			for (int k = i * i; k <= MAX; k += i)
				prime[k] = 1;
		}
	}
}

int main(void)
{
	makePrime();

	squreSum[2] = primeSum[2] = 1;

	for (int i = 3; i <= MAX;i++)
	{
		if (!prime[i]) primeSum[i] = primeSum[i - 1] + 1;
		else primeSum[i] = primeSum[i - 1];

		if (!prime[i] && (i % 4) == 1) squreSum[i] = squreSum[i - 1] + 1;
		else squreSum[i] = squreSum[i - 1];
	}

	while (1)
	{
		scanf("%d %d", &L, &U);
		if (L == -1 && U == -1) break;

		// 1) L은 자연수
		// 2) L만 음수
		// 3) 둘 다 음수

		if (L >= 1) printf("%d %d %d %d\n", L, U, primeSum[U] - primeSum[L - 1], squreSum[U] - squreSum[L - 1]);
		else if (L < 1 && U >= 0) printf("%d %d %d %d\n", L, U, primeSum[U], squreSum[U]);
		else if (L < 1 && U < 0) printf("%d %d %d %d\n", L, U, 0, 0);
	}

	return 0;
}