c - 如何使该代码算法高效？使用该算法后的代码将是什么？如何避免该程序超出时间限制？

Question

我有这个问题:

一些正整数可以用一个或多个连续素数的和来表示。一个给定的正整数有多少这样的表示？

比如整数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;
}

Answer 1

你的代码超时是因为你一直在重新计算你已经知道的东西:

1. 您正在为每个查询重新计算所有质数(您可以在查询开始之前预先计算所有需要的素数)

2. 你正在重新计算你已经知道的东西。 (即如果有要求对某个整数 x 的表示进行计数的查询，以及然后其他一些查询也问同样的事情你真的需要再次计算答案吗？)

建议:

1. 只有 10000 个可能的查询，所以只需创建数组answer[10001] 并填写所有可能的答案。

2. 10000 并不多，所以您甚至可以将所有答案保存在文件中，将其硬编码为代码中的数组，因此所有查询都将在每个查询 O(1)