我有这个问题:
一些正整数可以用一个或多个连续素数的和来表示。一个给定的正整数有多少这样的表示?
比如整数53有5+7+11+13+17和53两种表示法,整数41有2+3+5+7+11+13、11+13+17、41三种表示法. 整数3只有一种表示,就是3。整数20没有 这样的陈述。
请注意,被加数必须是连续的质数,因此 7 + 13 和 3 + 5 + 5 + 7 都不是整数 20 的有效表示。
任务是编写一个程序,报告给定正整数的表示数量。
示例输入:
2
3
17
41
20
666
12
53
0
示例输出:
1
1
2
3
0
0
1
2
我用seive方法得到素数数组p[10011]。 我的代码是:
#include <stdio.h>
int main()
{
int n, i, j, k, l, sum, count, ara[10011], d[10011];
while (-1)
{
for (i = 2; i <= n; i++)
{
ara[i] = 0;
}
l = 0;
while (1)
{
k = 0;
scanf("%d", &n);
int p[n];
count = 0;
for (i = 2; i <= n; i++)
{
if (ara[i] == 0)
{
for (j = 2 * i; j <= n; j += i)
{
ara[j] = 1;
}
}
}
for (i = 2; i <= n; i++)
{
if (ara[i] == 0)
{
p[k++] = i;
}
}
for (i = 2; i <= n; i++)
{
if (ara[i] == 0)
{
p[k++] = i;
}
}
for (i = 0; i < k; i++)
{
sum = 0;
for (j = i; j < k; j++)
{
sum += p[j];
if (sum == n)
{
count++;
break;
}
}
}
d[l] = count;
if (n == 0)
break;
l++;
}
for (i = 0; i < l; i++)
{
printf("%d\n", d[i] / 2);
}
}
return 0;
}
最佳答案
你的代码超时是因为你一直在重新计算你已经知道的东西:
您正在为每个查询重新计算所有质数(您可以 在查询开始之前预先计算所有需要的素数)
你正在重新计算你已经知道的东西。 (即如果有 要求对某个整数 x 的表示进行计数的查询,以及 然后其他一些查询也问同样的事情你真的需要再次计算答案吗?)
建议:
只有 10000 个可能的查询,所以只需创建数组 answer[10001] 并填写所有可能的答案。
10000 并不多,所以您甚至可以将所有答案保存在文件中, 将其硬编码为代码中的数组,因此所有查询都将在 每个查询 O(1)
关于c - 如何使该代码算法高效?使用该算法后的代码将是什么?如何避免该程序超出时间限制?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55400917/