C中的Euler #7项目:使用诸如Eratosthenes筛子之类的方法查找10001素数

Question

我在C中得到了Euler #7项目的一个解决方案(找到10,001素数)。我自己想出了一个非常简单的算法(据我所知，它与埃拉托斯提尼筛相似，如果不是完全相同的话)。

#include <stdio.h>

#include <stdlib.h>

long prime_finder(int amount_of_primes);

int main(void)
{
int amount_of_primes = 0;

printf("How many primes would you like?\n");
scanf("%d", &amount_of_primes);

printf("%d: %ld\n", amount_of_primes, prime_finder(amount_of_primes));

return 0;
}

long prime_finder(int amount_of_primes)
{
int total_primes_found = 0;

long * primes = malloc(sizeof(long) * amount_of_primes);

for(int i = 0;i < amount_of_primes; i++) //set everything to 0
{
    primes[i] = 0;
}

for(long i = 1; total_primes_found < amount_of_primes;i++) //find the primes
{
    if(i<14) //cheat a little for the first primes
    {
        switch (i)
        {
            case 1:
                break;

            case 2:
                primes[total_primes_found++] = 2;
                break;

            case 3:
                primes[total_primes_found++] = 3;
                break;

            case 5:
                primes[total_primes_found++] = 5;
                break;

            case 7:
                primes[total_primes_found++] = 7;
                break;

            case 11:
                primes[total_primes_found++] = 11;
                break;

            case 13:
                primes[total_primes_found++] = 13;
                break;

            default:
                break;
        }
    }

    else //if it is a larger number
    {
        if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 
|| i % 7 == 0 || i % 11 == 0 || i % 13 == 0) /*makes the program a little quicker if the
*current number divides by a low number like 2 or 3*/
        {
            goto End;
        }

        else
        {
            for(int j = 0; j < total_primes_found; j++) //the brute force part of the program
            {
                if(i % primes[j] == 0)
                {
                    goto End;
                }
            }

            primes[total_primes_found++] = i;
        }

        End:;

    }
}

for(int i = 0 ; i < amount_of_primes - 1 ; i++)
    printf("%d: %ld\n", i+1, primes[i]);

return primes[amount_of_primes - 1];
}

Answer 1

您的代码使用的是试用部门(i % primes[j] == 0)，因此它与埃拉托斯提尼筛完全不同--也与任何主要的筛子完全不同。

质数筛的核心思想是，你有某种数组，每个候选数字都有一个标志--筛子--并且这个数组中的所有非素数都会以某种方式被剔除，这样剩下的任何东西都必须是质数。

Eratosthenean筛分的特点是在击打过程中避免乘法和/或除法；一个数字的倍数是通过反复加法来列举的。这就是为什么它可以比其他方法快几个数量级的原因。

审判部门本身没有什么问题，只要你觉得足够快就能达到你的目的。如果欧拉问题描述要求100000,001质数，那么事情看起来就不一样了，而且你需要很大的耐心来处理基于审判分工的方法。这样你就可以更快地编写一个很好的筛子，而不是等待试筛完成.

下一次，从最简单、最直接的思想实现开始，忽略那些假设的优化。不要开始‘优化’，直到你有证据证明它是必要的，并保持优化，只有当衡量的改善远远超过你的源代码的丑陋结果。如果您做了一些度量，那么您会发现，只有当前“优化”的显著效果才会使代码不可读。

从最简单、最干净的绘制算法开始，可能会帮助您避免错误，如尝试除以素数2。13两次(第一次显式地在分支语句中，然后在检查已发现素数数组时再次隐式地检查)。

另外，为了证明一个数字的合成性，你只需要检查这个数字的平方根上的潜在因素。您正在检查小于该数目的所有素数(即到目前为止找到的所有素数)，这比所需的要多得多。

注意:显式试用除以几个最小的素数确实是一个有效的优化，也可以在工业强度代码中找到。这是因为用常量除法使编译器能够选择比实际除法更有效的方法，比如使用乘法和移位，或者测试位0来计算x % 2。然而，就像所有的优化一样，它不仅需要有效性的证明，而且还需要必要的证明才能做到这一点。