社区讨论

求助站外题

学术版参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo8j8emy
此快照首次捕获于
2023/10/27 19:30
2 年前
此快照最后确认于
2023/10/27 19:30
2 年前
查看原帖
题目描述
求第n个素数最多能分解成几个不同的奇素数之和。
输入格式
输入n
输出格式
输出第n个素数最多能分解成几个素数之和(不包括自身)。 若无法分解,输出-1。
输入输出样例
输入 #1 6
输出 #1 -1
输入 #2 12701618
输出 #2 6966
说明/提示 n<2*10^7
时间限制 50ms
(验证码279R祭)
CPP
#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;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...