查找给定整数之后的下一个素数

Question

我创建了一个函数，返回大于或等于作为参数的数字的下一个素数。我的代码运行良好，但我发现它非常慢。

测试套件几乎需要60年代的时间，我想要不到10秒。可以对代码进行优化以实现这一点吗？

码

#include <stdio.h>
int ft_is_prime(int nb)
{
     int    i;

    i = (int)nb - 1;
    if (nb <= 1)
        return (0);
    while (i > 1)
    {
        if (nb % i == 0)
            return (0);
        i--;
    }
    return (1);
}

int ft_find_next_prime(int nb)
{

    while (ft_is_prime(nb) == 0)
    {
        ft_is_prime(nb);
        nb++;
    }
    return (nb);
}

测试

int main()
{
    printf("%d -> %d\n", -1868, ft_find_next_prime(-1868));
    printf("%d -> %d\n", 0, ft_find_next_prime(0));
    printf("%d -> %d\n", 1, ft_find_next_prime(1));
    printf("%d -> %d\n", 2, ft_find_next_prime(2));
    printf("%d -> %d\n", 7853, ft_find_next_prime(7853));
    printf("%d -> %d\n", 78989, ft_find_next_prime(78989));
    printf("%d -> %d\n", 2147483643, ft_find_next_prime(2147483643));
    printf("%d -> %d\n", 2147483645, ft_find_next_prime(2147483645));
    printf("%d -> %d\n", 2147483646, ft_find_next_prime(2147483646));
    printf("%d -> %d\n", 2147483647, ft_find_next_prime(2147483647));
    printf("%d -> %d\n", 203785, ft_find_next_prime(203785));
    printf("%d -> %d\n", 14357, ft_find_next_prime(14357));
    printf("%d -> %d\n", 389654, ft_find_next_prime(389654));
    printf("%d -> %d\n", 356376, ft_find_next_prime(356376));
    printf("%d -> %d\n", 111641, ft_find_next_prime(111641));
    printf("%d -> %d\n", 139803, ft_find_next_prime(139803));
    printf("%d -> %d\n", 98368, ft_find_next_prime(98368));
    printf("%d -> %d\n", 172597, ft_find_next_prime(172597));
    printf("%d -> %d\n", 178697, ft_find_next_prime(178697));
    printf("%d -> %d\n", 295994, ft_find_next_prime(295994));
    printf("%d -> %d\n", 66107, ft_find_next_prime(66107));
    printf("%d -> %d\n", 348224, ft_find_next_prime(348224));
    printf("%d -> %d\n", 424018, ft_find_next_prime(424018));
    printf("%d -> %d\n", 182868, ft_find_next_prime(182868));
    printf("%d -> %d\n", 279638, ft_find_next_prime(279638));
    printf("%d -> %d\n", 215132, ft_find_next_prime(215132));
    printf("%d -> %d\n", 130734, ft_find_next_prime(130734));
    printf("%d -> %d\n", 254567, ft_find_next_prime(254567));
    printf("%d -> %d\n", 287850, ft_find_next_prime(287850));
    printf("%d -> %d\n", 101486, ft_find_next_prime(101486));
    printf("%d -> %d\n", 338034, ft_find_next_prime(338034));
    printf("%d -> %d\n", 367221, ft_find_next_prime(367221));
    printf("%d -> %d\n", 352888, ft_find_next_prime(352888));
    printf("%d -> %d\n", 296057, ft_find_next_prime(296057));
    printf("%d -> %d\n", 420476, ft_find_next_prime(420476));
    printf("%d -> %d\n", 337541, ft_find_next_prime(337541));
    printf("%d -> %d\n", 269965, ft_find_next_prime(269965));
    printf("%d -> %d\n", 262287, ft_find_next_prime(262287));
    printf("%d -> %d\n", 298128, ft_find_next_prime(298128));
    printf("%d -> %d\n", 81045, ft_find_next_prime(81045));
    printf("%d -> %d\n", 6816, ft_find_next_prime(6816));
    printf("%d -> %d\n", 200353, ft_find_next_prime(200353));
    printf("%d -> %d\n", 87717, ft_find_next_prime(87717));
    printf("%d -> %d\n", 275623, ft_find_next_prime(275623));
    printf("%d -> %d\n", 20140, ft_find_next_prime(20140));
    printf("%d -> %d\n", 145069, ft_find_next_prime(145069));
    printf("%d -> %d\n", 309422, ft_find_next_prime(309422));
    printf("%d -> %d\n", 288966, ft_find_next_prime(288966));
    printf("%d -> %d\n", 196808, ft_find_next_prime(196808));
    printf("%d -> %d\n", 408696, ft_find_next_prime(408696));
    printf("%d -> %d\n", 308434, ft_find_next_prime(308434));
    printf("%d -> %d\n", 234200, ft_find_next_prime(234200));
    printf("%d -> %d\n", 12514, ft_find_next_prime(12514));
    printf("%d -> %d\n", 363758, ft_find_next_prime(363758));
    printf("%d -> %d\n", 257776, ft_find_next_prime(257776));
    printf("%d -> %d\n", 312563, ft_find_next_prime(312563));
    printf("%d -> %d\n", 757, ft_find_next_prime(757));
    printf("%d -> %d\n", 398583, ft_find_next_prime(398583));
    printf("%d -> %d\n", 36608, ft_find_next_prime(36608));
    printf("%d -> %d\n", 35590, ft_find_next_prime(35590));
    printf("%d -> %d\n", 174862, ft_find_next_prime(174862));
    printf("%d -> %d\n", 409874, ft_find_next_prime(409874));
    printf("%d -> %d\n", 68893, ft_find_next_prime(68893));
    printf("%d -> %d\n", 87838, ft_find_next_prime(87838));
    printf("%d -> %d\n", 284334, ft_find_next_prime(284334));
    printf("%d -> %d\n", 48416, ft_find_next_prime(48416));
    printf("%d -> %d\n", 32034, ft_find_next_prime(32034));
    printf("%d -> %d\n", 125232, ft_find_next_prime(125232));
    printf("%d -> %d\n", 418100, ft_find_next_prime(418100));
    printf("%d -> %d\n", 312630, ft_find_next_prime(312630));
    printf("%d -> %d\n", 288568, ft_find_next_prime(288568));
    printf("%d -> %d\n", 398662, ft_find_next_prime(398662));
    printf("%d -> %d\n", 46407, ft_find_next_prime(46407));
    printf("%d -> %d\n", 121678, ft_find_next_prime(121678));
    printf("%d -> %d\n", 406867, ft_find_next_prime(406867));
    printf("%d -> %d\n", 61269, ft_find_next_prime(61269));
    printf("%d -> %d\n", 315739, ft_find_next_prime(315739));
    printf("%d -> %d\n", 271203, ft_find_next_prime(271203));
    printf("%d -> %d\n", 192870, ft_find_next_prime(192870));
    printf("%d -> %d\n", 114535, ft_find_next_prime(114535));
    printf("%d -> %d\n", 173417, ft_find_next_prime(173417));
    printf("%d -> %d\n", 248682, ft_find_next_prime(248682));
    printf("%d -> %d\n", 306029, ft_find_next_prime(306029));
    printf("%d -> %d\n", 108921, ft_find_next_prime(108921));
    printf("%d -> %d\n", 210815, ft_find_next_prime(210815));
    printf("%d -> %d\n", 252289, ft_find_next_prime(252289));
    printf("%d -> %d\n", 72584, ft_find_next_prime(72584));
    printf("%d -> %d\n", 297710, ft_find_next_prime(297710));
    printf("%d -> %d\n", 27544, ft_find_next_prime(27544));
    printf("%d -> %d\n", 373150, ft_find_next_prime(373150));
    printf("%d -> %d\n", 219888, ft_find_next_prime(219888));
    printf("%d -> %d\n", 156579, ft_find_next_prime(156579));
    printf("%d -> %d\n", 271274, ft_find_next_prime(271274));
    printf("%d -> %d\n", 295751, ft_find_next_prime(295751));
    printf("%d -> %d\n", 207022, ft_find_next_prime(207022));
    printf("%d -> %d\n", 143794, ft_find_next_prime(143794));
    printf("%d -> %d\n", 390643, ft_find_next_prime(390643));
    printf("%d -> %d\n", 186808, ft_find_next_prime(186808));
    printf("%d -> %d\n", 230330, ft_find_next_prime(230330));
    printf("%d -> %d\n", 175035, ft_find_next_prime(175035));
    printf("%d -> %d\n", 101832, ft_find_next_prime(101832));
    printf("%d -> %d\n", 205261, ft_find_next_prime(205261));
    printf("%d -> %d\n",389070, ft_find_next_prime(389070));
    printf("%d -> %d\n", 397788, ft_find_next_prime(397788));
    printf("%d -> %d\n", 6117, ft_find_next_prime(6117));
    printf("%d -> %d\n", 169448, ft_find_next_prime(169448));
    printf("%d -> %d\n", 393706, ft_find_next_prime(393706));
    printf("%d -> %d\n", 286195, ft_find_next_prime(286195));
    printf("%d -> %d\n", 334329, ft_find_next_prime(334329));
    printf("%d -> %d\n", 184829, ft_find_next_prime(184829));
}

Answer 1

使用ft_find_next_prime()可以做得更好。

首先，没有质数< 2，所以如果你从那里开始，质数是2。

第二，所有素数>2都是奇数，所以不需要考虑偶数。

与算法无关的一个要点是，测试布尔值是否相等通常是不明智的。只需在条件测试中直接使用该值即可。

结合“顶级大师的观点”，产生：

int ft_find_next_prime(int nb)
{
    if (nb <= 2) return 2; /*early numbers*/
    nb |= 1; /*Ensure it is odd*/
    while (!ft_is_prime(nb))
    {
        nb += 2;
    }
    return nb;
}

关于ft_is_prime()没有明确提出的问题:您应该检查从最可能到最少。也就是说，从2开始，而不是nb-1 (甚至sqrt(nb))。尽管无论哪种方法都是O(n)或O(sqrt(n))，您将获得更快的复合结果。

您可以做的另一个奇怪的改变是:我的ft_find_next_prime实现从不将偶数传递给ft_is_prime。因此，您可以创建一个ft_is_prime_given_odd函数并跳过@Gh0st的第二个优化版本中的第一个测试。

Answer 2

函数ft_is_prime具有复杂性O(n)，由于您的输入可能很大，所以它非常慢。简单的优化是检查除数到所测试的数字的平方根。有检验素数的其他算法，但我认为在这种情况下它已经足够好了。我还会制作nb long long。它可以以这样的方式实现：

int ft_is_prime(long long nb) {
    if (nb <= 1)
        return 0;
    for(long long i = 2; i*i <= nb; i++){
        if(nb % i == 0){
            return 0;
        }
    }
    return 1;
}

您还可以先检查2除以nb，然后它看起来是这样的(它不会改变复杂性)：

if(nb % 2 == 0)
    return 0;
for(long long i = 3; i*i <= nb; i+=2){
    if(nb % i == 0){
        return 0;
    }
}

Answer 3

int ft_is_prime(int nb)

这是一个布尔函数，因此我们应该记录如下：

#include <stdbool.h>

bool ft_is_prime(int nb)

int i；i=(Int)nb-1；

我们可以组合声明和赋值，并且不需要强制转换(因为nb已经是int类型了)：

int i = nb - 1;

return (0);

这里不需要括号--普通的旧return 0;更简单、更易读。

而(i > 1)

通过试用部门测试原始性已经很慢了，但是我们已经通过首先测试最大的候选因素来使它变得更慢。如果我们从最小的候选人开始，我们会更快地消除数字。当我们到达nb的平方根时，我们可以停止：

#include <math.h>

bool ft_is_prime(int nb)
{
    if (nb < 2)
        return false;

    /* add one to ensure round-up */
    const int limit = (int)sqrt(nb) + 1;
    for (int i = 2;  i <= limit;  ++i) {
        if (nb % i == 0) {
            return false;
        }
    }

    /* no factors found => must be prime */
    return true;
}

如果不考虑除2以外的偶数，我们可以走得更快：

    if (nb % 2 == 0) {
        return false;
    }

    /* add one to ensure round-up */
    const int limit = (int)sqrt(nb) + 1;
    for (int i = 3;  i <= limit;  i += 2) {
        if (nb % i == 0) {
            return false;
        }
    }

使用sqrt()的代码有点问题，因为它使用浮点算法，这是不准确的(需要使用+1)，而且在许多平台上，要比整数算法慢得多。但是，我们可以简单地使用i <= nb / i，这不应该导致额外的除法:一个好的优化编译器将使用一个操作来计算下一行的nb / i和nb % i。

改进的代码

这些更改将测试套件的运行时间从超过1分钟提高到0.01秒以下(都是用gcc -O3编译的)。

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

bool ft_is_prime(int nb)
{
    if (nb < 2 || nb % 2 == 0 && nb != 2) {
        return false;
    }

   for (int i = 3;  i <= nb/i;  i += 2) {
        if (nb % i == 0) {
            return false;
        }
    }

    /* no factors found => must be prime */
    return true;
}

int ft_find_next_prime(int nb)
{
    if (nb < 2) {
        return 2;
    }

    while (!ft_is_prime(nb)) {
        ++nb;
    }
    return nb;
}

为了进一步改进，我们应该放弃尝试性划分，转而使用更好的算法，也许使用素数轮。