使用此主要查找器功能改进和绕过超时错误测试的任何建议？

Question

我应该创建一个函数来为给定数字找到最接近的下一个素数，我的意思是即使算法写得不好而且非常慢（可能是最慢的），但它完成了任务，问题是应该评估我的东西的程序因超时错误而拒绝它，他一次给了它一堆数字，他希望它们在 10 秒内全部解决，所以问题是你可以提出任何改进建议可以快进我可怜的曲折吗？ (for 不允许)

int is_prime(int nb)
{
    int i;
    /* if negative terminate */
    if (nb <= 1)
        return (0);
    /* start from first prime */ 
    i = 2;
   /* primes equals zero only when divisible by 1 and theme-selves */
    while (nb % i != 0)
        i++;
    /* if i divides nb, we see if i is the nb we looking for */
    if (i == nb)
        return (1);
    else
        return (0);
}

int find_next_prime(int nb)
{
    int i;

    i = 0;
    /*keep looking for primes one by one */
    while (!is_prime(nb + i))
        i++;
    return (nb + i);
}

Answer 1

您错过了两个最常用的提高速度的技巧。

你只需要检查数字的平方根
一旦你检查了 2，你只需要检查从 3 开始的每个其他号码。

Answer 2

最简单的速度改进是检查直到 n 的平方根的除数，而不是检查直到 n 的所有除数。这使算法从 O(nb) 到 O(sqrt(nb))。

考虑 is_prime(2147483647)。 OP 的方法大约需要 2147483647 次迭代。测试平方根 46341 大约快 46,000 倍。

// while (nb % i != 0) i++;
// if (i == nb) return (1);
// else return (0);

// While the divisor <= quotient (or until the square root is reached)
while (i <= nb/i) {
  if (nb%i == 0) return 1;
  i++;
}
return 0;

避免 i*i <= nb 测试，因为 i*i 可能会溢出。
避免 sqrt(nb) 因为涉及大量浮点/int 问题。
注意：优秀的编译器会查看附近的 nb/i; nb%i 并计算它们的时间成本。

还有很多其他的改进是可能的，但我想专注于一个简单但影响很大的改进。当想要提高速度时，请专注于降低复杂性的顺序 O() and not linear improvements. Is premature optimization really the root of all evil?

使用此主要查找器功能改进和绕过超时错误测试的任何建议？

any suggestions to improve and bypass timeout error test with this prime finder function?

c

algorithm

performance

primes