相关疑难解决方法(0)

这是我能提出的最佳算法.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

可以做得更快吗？

此代码有一个缺陷:由于numbers是无序集,因此无法保证numbers.pop()从集中删除最小数字.然而,它对某些输入数字起作用(至少对我而言):

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

我正在尝试欧拉计划的第 10 题，即 2,000,000 以下所有素数的总和。我尝试过使用 Python 实现埃拉斯托坦筛法，我编写的代码对于 10,000 以下的数字非常有效。

然而，当我尝试求更大数字的素数之和时，代码运行时间太长（求 100,000 以内的素数之和需要 315 秒）。该算法显然需要优化。

是的，我看过这个网站上的其他帖子，比如列出 N 以下所有素数的最快方法，但是那里的解决方案对代码如何工作的解释很少（我仍然是初学者程序员），所以我无法实际上向他们学习。

有人可以帮助我优化我的代码，并清楚地解释它是如何工作的吗？

这是我的代码：

primes_below_number = 2000000 # number to find summation of all primes below number
numbers = (range(1, primes_below_number + 1, 2)) # creates a list excluding even numbers
pos = 0 # index position
sum_of_primes = 0 # total sum
number = numbers[pos]
while number < primes_below_number and pos < len(numbers) - 1:
    pos += 1
    number = numbers[pos] # …

我用C语言编写了该程序，用于测试数字是否为质数。我还不了解算法的复杂性以及所有有关Big O的知识，因此我不确定将迭代和递归相结合的方法是否比使用纯迭代方法更有效。

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

typedef struct primenode{
    long int key;
    struct primenode * next;
}primenode;

typedef struct{
    primenode * head;
    primenode * tail;
    primenode * curr;
    unsigned long int size;
}primelist;

int isPrime(long int number, primelist * list ,long int * calls, long int * searchcalls);
primenode * primelist_insert(long int prime, primelist * list);
int primelist_search(long int searchval, primenode * searchat, long int * calls);
void primelist_destroy(primenode * destroyat);

int main(){
    long int …