BOJ 13827 Space Coconut Crab II
BOJ 13827 Space Coconut Crab II
문제 내용
양의 정수 가 주어질 때, 세 변의 길이가 각각 소수이면서 세 변의 길이의 합이 인 서로 다른 삼각형의 개수를 구하세요. 세 변의 길이의 순서를 바꿨을 때 같은 것은 서로 같은 것입니다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있습니다. 테스트는 0으로 종료됩니다.
각 테스트 케이스에 대해, 의 값이 한 줄에 주어집니다. ()
출력
각 테스트 케이스에 대해 문제의 정답을 출력합니다.
문제 풀이
스포일러
일단 3만 이하의 소수를 모두 구합니다. 이는 에라토스테네스의 체로 구해도 되고, 단순히 루트까지 나눠보기로 구해도 됩니다. 이렇게 구한 소수의 개수는 3244개입니다.
이제 각각의 에 대해 다음과 같이 개수를 셀 수 있습니다.
- 에 대해, 번째 소수와 번째 소수를 가져옵니다.
- 세 번째 변의 길이가 다음의 조건을 모두 충족하면 개수에 1을 더합니다.
- 세 번째 변의 길이는 소수입니다.
- 세 번째 변의 길이는 번째 소수 이상이면서, 번째 소수와 번째 소수의 합보다 작습니다.
이때의 시간복잡도는 소수의 개수를 이라고 할 때 입니다. 가 여러 개이지만 시간 제한은 넉넉하게 주어집니다.
Last updated on