社区讨论
求助站外题
学术版参与者 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 条回复,欢迎继续交流。
正在加载回复...