题目描述

求第n个素数最多能分解成几个不同的奇素数之和。

输入格式

输入n

输出格式

输出第n个素数最多能分解成几个素数之和（不包括自身）。 若无法分解，输出-1。

输入输出样例

输入 #1 6

输出 #1 -1

输入 #2 12701618

输出 #2 6966

说明/提示 n<2*10^7

时间限制 50ms

(验证码279R祭)

#include <cstdio>
#include <cstring>

bool isPrime[1000000010];
long long Prime[60000010], cnt = 0;

void GetPrime(long long n)
{
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[1] = 0;

    for(long long i = 2; i <= n; i++)
    {
        if(isPrime[i]) 
            Prime[++cnt] = i; 
        for(long long j = 1; j <= cnt && i*Prime[j] <= n; j++) 
        {
            isPrime[i*Prime[j]] = 0;

            if(i % Prime[j] == 0)
                break; 
        }
    }
}

int main()
{
    long long n=1000000000;
    GetPrime(n);
        long long k;
        scanf("%lld",k);
        long long c=2;
            c=2;
            long long m=Prime[k];
        while(m-Prime[c]!=0)
        {
            if(m-Prime[c]<0)
            {
                c=-1e9;break;
            }
            c++,m-=Prime[c];
        }
        if(c!=-1e9)
        printf("%lld\n", c);

    return 0;
}