如何减少运行时间？（涉及IT技术）

Question

这里是我尝试解决的问题链接：http://acm.timus.ru/problem.aspx?space=1&num=1086 我的方法如下：

#include <stdio.h>
#include <math.h>

int main()
{
    int n, i, m, p;

    scanf("%d", &n);

    for(i = 0; i < n; i++)
    {
        scanf("%d", &m);

        p = find_prime(m);
        printf("%d\n", p);
    }

    return 0;
}

int find_prime(int a)
{
    int i, p = 1, t, prime[15000], j;
    prime[0] = 2;

    for(i = 0; i < a; )
    {
        if(p == 2)
        {
            p++;
        }else
        {
            p = p + 1;
        }
        t = 0;
        for(j = 0; prime[j] <= sqrt(p); j++)
        {
            if(p%prime[j] == 0 && p != 2)
            {
                t = 1;
                break;
            }
        }
        if(t != 1)
        {
            i++;
            prime[i] = p;
        }
    }

    return p;
}

我知道算法没问题，它能够得出正确的答案。但是我总是遇到“超时”错误。我无法将运行时间缩短到2秒以内，它总是等于2.031秒。我尝试了其他几种方法，例如，我遍历所有数字直到找到第m个质数，我尝试跳过大于2的偶数，但我仍然会得到2.031秒的运行时间。

我该怎么办？

- lucid.dreamer

---

可能是重复的问题：如何在不使用我的函数chk prime的情况下找到质数，因为我希望优化我的算法。 - user4580220

你可以使用 埃拉托斯特尼筛法。 - FabienAndre

你认为 if(p == 2) { p++; } else { p = p + 1; } 的两个分支之间的行为差异是什么？在我看来，无论其初始值如何，p 都会增加一。而且我注意到 Ed Heal 在他的 不算答案的回答 中指出了这一点。 - Jonathan Leffler

由于等待用户输入一些数字序列需要大量时间，与实际执行相比似乎不切实际，因此将注意力集中在find_prime()函数的执行时间上似乎不现实。 - user3629249

当调用scanf()（或任何该系列函数）时，代码应始终检查返回的值（而不是参数值），以确保操作成功。 - user3629249

Answer 1

您用于素数的缓冲区不需要是每次重新计算的局部变量。

您可以尝试通过将缓冲区存储在全局范围内并使用全局计数器来跟踪到目前为止已经计算了多少个质数以及最大请求的数字是哪一个来记忆化。

如果下一个要求的数字比先前的最大值小，则应返回相应的预计算数字。如果下一个数字比先前的最大值大，则将其作为新的最大值 - 并尝试从上次离开的地方开始计算。

- Theodoros Chatzigiannakis

---

为什么不预先计算小于15000的所有质数呢？他有64 MB的内存可供使用。那应该足够了。 - Seamus

@Seamus 我故意描述了一个通用的解决方案。当然，对于我们所讨论的规模，你关于预先计算的建议是完全有效的（并且很可能更具性能）。在实际情况下，可能两种技术的结合都是可行的。 - Theodoros Chatzigiannakis

@seamus，那不会花费很多时间吗？而且我输入的数字不能大于15000，而不是质数。 - lucid.dreamer

@lucid.dreamer 供参考，使用Python中的朴素算法计算埃拉托斯特尼筛法直到163,841（第15,000个质数），我花费了60毫秒。因此，不会花费太多时间。 - FabienAndre

这是我的新方法：我确定了最大的输入（假设为n），然后计算出所有第n个质数之前的质数，最后只需查找我需要的质数。仍然需要相同的时间。 - lucid.dreamer

Answer 2

移除

  if(p == 2)
    {
        p++;
    }else
    {
        p = p + 1;
    }

将其替换为

p++

- Ed Heal

---

我已经尝试过了，但没有任何好处。所以我想如果我能跳过那些明显不是质数的整数，可能会节省更多时间。 - lucid.dreamer

Answer 3

据我理解，

问题是要找到比之前所有输入数字的总和更大的下一个质数。

这意味着有一定的期望。

1) the sum of the prior input numbers is available in find_prime(). 
2) for simplification, the last found prime number is available in find_prime().  

这些期望都没有被实现。

然后在find_prime()函数中有一个60千字节的数组在堆栈上。

建议将其移动到文件全局位置并包含'static'修饰符。

将先前输入的总和移动到文件全局位置，以便始终可用。

为了整体速度，

首先计算数组中的所有质数，从而填充数组的质数值。 然后

1) add new input to sum, 
2) index into array using sum. 
3) return value found in array.

- user3629249