$1$부터 $N$까지의 합은 항상 합성수일까?

한 줄 요약: $N \geq 3$부터 합성수다.

 

$1$부터 $N$까지의 합은 간단하게 $S(N) = \frac{N(N+1)}{2}$로 나타낼 수 있다. 합성수는 소수와 소수의 곱 혹은 소수와 합성수의 곱 혹은 합성수와 합성수의 곱이다.

 

1. $N$이 $1$이라면 $S(1) = 1$이므로 이는 소수도 아니고 합성수도 아니다.

2. $N$이 $2$라면 $S(2) = \frac{2 \times 3}{2} = 1 \times 3$이므로 소수다.

3. $N$이 $3$보다 크거나 같다면 $S(N) = \frac{N(N+1)}{2}$에서 $N$은 $3$보다 크거나 같고 $N+1$도 $4$보다 크거나 같다. 이는 둘 중에 하나가 짝수여서 $2$로 나누어떨어진다고 가정했을 때, $N = 2$와 같이 $1$이 되지 않는다. 따라서 소수와 소수의 곱 혹은 소수와 합성수의 곱 혹은 합성수와 합성수의 곱이기 때문에 합성수이다.

 

관련 문제

BOJ 19408

BOJ 30021