Boj 1644) 소수의 연속합

방법 1

백준 1644

설명

소수를 미리 구해놔야해서 에라토스테네스의 체를 사용한다.

그리고 투 포인터를 이용해 연속합을 구한다. 주의할 점은 누적합을 구하는 것이므로 두 포인터가 양 끝이 아니라 한쪽에서 시작한다는 것 이다.

시간 복잡도

O(N)

코드

const int MAX_IN = 4000001;
bool bNonPrimes[MAX_IN];

// 에라토스테네스의 체
void Prime(int limit)
{
    bNonPrimes[1] = 1;  // 1 is not prime
    for (int i = 2; i < limit; i++) {   // primes => 0;
        if (bNonPrimes[i] == 1) continue;
        for (int j = 2 * i; j < limit; j += i)
            bNonPrimes[j] = 1;
    }
}

inline void NextPrime(int& in)
{
    while (in >= 0 && bNonPrimes[in]) in--;
}

int main()
{
    int input;
    cin >> input;
    
    Prime(input + 1);
    
    int sum = 0, ans = 0;
    int end = input + 1, begin = end;
    
    while (begin >= 0 && end >= 0)  // 사실 이중포문 해도 돌아감
    {
        if (bNonPrimes[begin]) NextPrime(begin);
        if (bNonPrimes[end])   NextPrime(end);
    
        if (sum < input)      sum += begin--;
        else if (sum > input) sum -= end--;
        else {
            ans++;
            sum -= end--;
            sum += begin--;
        }
    }
    cout << ans;
}

방법 2

설명

이중 for 문으로 구현할 수도 있음.

• 일정이상 수가 커지면 break 하는 방식으로 하면 됨
• 두 포인터 보다 중복되는 계산이 조금 더 섞여있지만 엄청 느려지진 않음.
  • 중복해서 계산할게 n/2, n/3, n/4 ... n/n 이런 배열을 따를 것이기 때문.
  • =NLogN
• 대신 이때는 소수만 모아놓은 배열을 따로 빼서 \(N\) 을 줄여줘야함.

시간복잡도

O(\(Nlog{N}\))

코드

const int MAX_IN = 4000001;
bool bNonPrimes[MAX_IN];
vector<int> primes;

void Prime(int limit)
{
    bNonPrimes[1] = 1;  // 1 is not prime
    for (int i = 2; i < limit; i++) {   // primes => 0;
        if (bNonPrimes[i] == 1) continue;
        for (int j = 2 * i; j < limit; j += i)
            bNonPrimes[j] = 1;
    }
    primes.push_back(0);
    for (int i = 2; i < limit; i++)
        if (!bNonPrimes[i]) primes.push_back(i);
}

int main()
{
    int input;
    cin >> input;
    
    Prime(input + 1);
    
    int ans = 0;
    
    for (int i = primes.size()-1; i >= 0; i--)
    {
        int sum = 0;
        for (int j = i; j >= 0; j--)
        {
            sum += primes[j];
            if (sum > input) break;
            else if(sum == input) {
                ans++;
                break;
            }
        }
    }
    cout << ans;
}