我应该创建一个函数，为给定的数字找到最接近的下一个素数，我的意思是，尽管算法写得很糟糕，速度很慢(可能是最慢的(，但它完成了任务，问题是应该评估我的东西的程序会以超时错误拒绝它，他一次给了它一堆数字，他希望在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);
}
最好的简单速度改进是检查n平方根以下的除数，而不是检查n以下的所有除数。这使得算法从O(nb(到O(sqrt(nb((。
考虑is_prime(2147483647)。OP的方法需要大约2147483647次迭代。平方根为46341的测试速度大约快46000倍。
// 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((，而不是线性改进。过早的优化真的是万恶之源吗？
你错过了提高速度的两个最常见的技巧。
- 您只需要检查数字的平方根
- 一旦你检查了2，你只需要从3开始每隔一个号码检查一次