[C/C++] 백준 #1644 소수의 연속합(수학)

이번 문제는 연속된 소수들의 합을 이 주어진 값으로 표현되면, 그러한 경우의 수를 계산하는 것입니다.

 

원래는 소수들의 누적합을 이용해서 푸는 것이 좋겠죠.  먼저 n보다 작거나 같은 소수들의 집합을 구합니다.  n이 30이라고 한다면 아래와 같은 소수들 리스트를 얻게 됩니다.

2

3

5

7

11

13

17

19

23

29

 

누적합은 다음과 같이 구할 수 있습니다.  우리는 이 누적합 테이블만 사용하면 됩니다.

2

5

10

17

28

41

58

77

80

109

 

이 누적합 테이블은 실제 연속된 합을 계산할 때 사용합니다.

제일 먼저 이분탐색을 이용해서 30을 찾습니다.  해당 값은 첫 소수부터 연속된 소수의 합이 30이 되는 경우입니다.  맨 처음 누적합에 0을 넣는다면 이 부분을 생략해도 됩니다.

 

이제 109부터 시작을 합니다.  109에서 30을 빼면 79이고, 이 수가 있는지 찾습니다.  없으면 다음 수인 80입니다.  30을 빼면 50입니다.  50이 있는지 찾습니다.  77의 경우는 47을 찾고, 58인 경우는 28을 찾습니다.  이 경우는 있으니 하나를 찾았죠.  41은 11을 찾아야하는데 없습니다.  28은 30보다 작으니 여기까지 하면 30인 경우에는 답이 1인 것을 알 수 있습니다.

 

소수를 찾는 알고리즘이 \(O(n \pi(n))\)인 관계로, 사실 위의 소수값을 찾는 알고리즘 효율은 크게 상관이 없습니다.

제 경우는 조금 더 복잡한 방법으로 찾았습니다.

 

1. n이 주어지면, 두 소수의 연속된 합이 n보다 작거나 같은 소수들을 구합니다.  이렇게함으로써 구해야할 소수들의 수를 줄입니다.

 

2. n이 홀수라면, n이 소수인지 검사합니다.  n이 소수이면, ans 값은 1이 되고, 그렇지 않다면, ans 값은 0으로 설정합니다.

 

3. 두개이상의 합을 계산하기 위해서 소수값이 n/2 지점에서부터 시작해서 소수들의 합을 구해나갑니다. 

n의 값이 30이라면 실제 소수는 17까지만 구했겠죠.

 

2

3

5

7

11

13

17

X

X

X

그러면 30의 중간값인 15인 지점을 찾습니다.  그러면 13이 찾아지죠.  13+17=30이므로 일단 하나를 찾았습니다.

그러면 17은 더 이상 합의 값으로는 사용이 안됩니다.  13부터 시작해서 11, 7을 더합니다.  31로 넘어갑니다.  그러면 13은 안됩니다.  13을 제거하고 현재 누적값 18에서 출발해서 5, 3, 2을 더합니다.  총 28인데, 끝까지 왔으며로 30의 답은 1개가 됩니다.

 

이 방법을 사용하면, 소수를 구할때에도 구해야할 소수의 최대값이 n/2를 넘는 처음 소수까지 구하면 되기때문에 대략 \(O(n \pi(n))\) 형태가 바뀌는 것은 아니지만 대략적으로 큰 수에 대해서 1/4 정도로 시간이 단축이 됩니다.  그 후에 합을 계산하는 과정에서 \(O(n)\)이므로 앞의 알고리즘보다 더 낫다고 판단할 수 있습니다.

 

아래는 제가 작성한 소스입니다.  지금 소스를 보니, 다소 불합리하게 짠 부분이 보입니다.  분명히 문제점은 보이는데, 당분간은 안 고칠 듯 합니다.  소스는 참조용으로만 봐주세요.

//------------------------------------------------------------------------------
//  baekjoon #1644 - Serial Sum of Prime Numbers
//      - by Aubrey Choi
//      - created at 2019-06-27
//------------------------------------------------------------------------------
#include <stdio.h>
#include <math.h>

int primes[300000]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,}, pc=15;
void makeprimes(int n)
{
    int p, i, s;
    for(p=53; p<=n-primes[pc-1];p+=2)
    {
        for(i=1,s=(int)sqrt(p);primes[i]<=s&&(p%primes[i]);i++);
        if(primes[i]>s) primes[pc++] = p;
    }
}

int main()
{
    int n, sum=10, ans=0, ex[]={0, 0, 1, 1, 0, 2, 0, 1, 1, 0, 1}, f=0, c=3;
    scanf("%d", &n);
    if(n <= 10) { printf("%d\n", ex[n]); return 0; }
    makeprimes(n);
    if(n&1)
    {
        int s = (int)sqrt(n);
        ans = 1;
        for(int i = 1; primes[i] <= s; i++)
        {
            if(n%primes[i] == 0)
            {
                ans = 0;
                break;
            }
        }
    }
    while(primes[f] < n/2)
    {
        while(c < pc && sum < n) sum += primes[c++];
        if(sum == n) ans++;
        sum -= primes[--c] + primes[f++];
    }
    printf("%d\n", ans);
}