c - 我怎样才能减少运行时间？

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 秒。

我该怎么办？

Answer 1

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

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

如果您请求的下一个数字小于之前的最大值，您应该回退到相应的预先计算的数字。如果下一个数字大于前一个最大值，则将其设为新的最大值 - 并尝试从上次中断的地方开始计算。