백준 29261 - 소수 세기 (C++)

문제

• 문제 링크

  
   BOJ 29261 - 소수 세기 
  

• 문제 요약

소수 $P$가 주어진다.
아래의 과정을 반복할 때, 지워진 수를 포함하여 한별이가 소수를 적는 최대 횟수를 구해보자.



칠판에 적힌 수 중, $p_1 + p_2 + 1$$($단, $p_1, p_2$는 소수$)$ 꼴로 표현되는 수가 있으면 그러한 수 중 하나를 골라 지우고, 대신에 $p_1$과 $p_2$를 적는다. 만약 고른 수에 대해서 가능한 $(p_1, p_2)$ 쌍이 여러 개 있으면 그런 쌍 중 하나를 고른다.

• 제한

TL : $1$ sec, ML : $1024$ MB




$2 ≤ P < 3,000,000$

알고리즘 분류

• 수학 (math)
• 정수론 (number_therory)
• 소수 판정 (primality_test)

풀이

식에서 $1$을 제하면 골드바흐의 추측을 적용해볼 수 있다.

어떤 짝수에 대해, 두 소수 $p_1, p_2$로 분리되는 경우의 수는 여러가지일 수 있다.

모든 상황을 가정하며 계산하는 것은 수의 범위가 작지 않아 $TLE$로 이어질 것 같고,
직관적으로 볼 때 $|p_1 - p_2|$ 가 가장 적도록 나누는 것이 최선이라고 생각했다.

그렇게 슬쩍 짜서 내보니 $AC$가 떠서 얼떨결에 $Proof$ $By$ $AC$ 가 됐는데, 명확한 증명은 어떻게 해야 할지 잘 모르겠다.. 암튼 맞았으면 된건가 $?$

이후 다른 코드들을 구경하던 중 수상하리만큼 길이가 짧은 $AC$ 코드들이 보였다.
보아 하니 식정리가 되어 $O(1)$ 풀이가 있었던 것.

오늘도 세상은 넓고 고수는 많다는 걸 깨달았다.

전체 코드

#include<bits/stdc++.h>
#define N 3000001
 
std::bitset <N> p;
 
int f(int x)
{
    if (x < 4) return 0;
 
    for (int i((x - 1) >> 1); !!~i; i--)
        if (!p[i] && !p[x - i - 1])
            return f(i) + f(x - i - 1) + 2;
}
int main()
{
    for (int i(2); i * i < N; i++)
        if (!p[i])
            for (int j(i* i); j < N; j += i)
                p[j] = 1;
 
    int n; std::cin >> n;
    std::cout << f(n) + 1;
}

comment

끝