需要帮助优化算法 – 所有素数的总和低于200万
我正在尝试做一个Project Euler问题。
我正在寻找2,000,000以下所有素数的总和。
这就是我的……
int main(int argc, char *argv[]) { unsigned long int sum = 0; for (unsigned long int i = 0; i %lu\n", sum); } int isPrime(int num) { if (num < 2) { return 0; } for (int i = 2; i < num; ++i) { if (num % i == 0) { return 0; } } return 1; } 运行需要很长时间，因此它不满足欧拉问题的一分钟运行时间规则 。
当我以10的限制运行时，它会得到正确的答案， 17就像在问题中一样。
我的猜测是有一些算法可以减少正在完成的工作。 问题是，我不知道它是什么。
有人可以指出我正确的方向吗？
谢谢。
当i从2到2000000 （或任何上限）时，一旦你确定i是素数，你就知道{2i, 3i, 4i, ..., ni}不是素数，其中ni <= 2000000 。
你不需要测试这些数字 - 你知道它们不是素数。
当您浏览testNumbers数组并从该列表中删除数字时，您现在知道的数字不是素数，您可以显着减少实际需要测试的数字。
是的，这是Eratosthenes的筛子。
你可以缩短寻找素数的时间。 有百万种方法可以做到这一点。 我认为你不需要测试直到num，但只需要测试sqrt（num），但这只会对你有所帮助（在实际素数上）
有统计方法可以检查质数是否实际为素数更快，并且只能在2 ^中错误一次….
寻找素数的最快方法是来自印度的研究人员，但我找不到这个链接。
你也可以看看这里：
维基
你可以通过传递到目前为止发现的素数数组来加速你的isPrime(int num)函数，并检查num是否是这些素数的倍数。 此外，您不需要循环到num ，只需要sqrt(num) 。
使用Atkin的筛子，它是Eratosthenes 链接筛的优化版本。
提示：使用BitArray和seive方法。
如果您无法弄清楚，请参阅代码 。代码是Java，但不难转换为C.
#include #include #include struct prime_list_t { long n; struct prime_list_t *next; }; void add_prime_list_t(struct prime_list_t** list, long n); void free_prime_list_t(struct prime_list_t** list); long count_prime_list_t(struct prime_list_t* list); long last_prime_list_t(struct prime_list_t* list); /* if one of the primes in list divides n, is not a prime */ int is_prime(struct prime_list_t* pl, long n) { struct prime_list_t* p; if(pl == NULL) { abort(); } p = pl; while(p != NULL) { if(n % p->n == 0) { return 1; } p = p->next; } return 0; } int main() { struct prime_list_t* pl = NULL; struct prime_list_t* p; long n_up = 2000000; long long p_sum = 0; long ppr; int done; /* add first prime number */ add_prime_list_t(&pl, 2); /* from now on add to this list up to the number of items */ done = 0; do { /* get the last prime plus one */ ppr = last_prime_list_t(pl) + 1; while(is_prime(pl, ppr) != 0) { ppr++; if(ppr >= n_up) { /* hit the upper limit */ done = 1; break; } } if(done) { break; } /* ppr is prime */ add_prime_list_t(&pl, ppr); /* display status */ printf("%ld numbers largest prime %ld\r", count_prime_list_t(pl), last_prime_list_t(pl)); } while(!done); p = pl; p_sum = 0; while(p) { // printf("%d ", p->n); p_sum += p->n; p = p->next; } printf("\nsum: %I64d\n", p_sum); free_prime_list_t(&pl); return 0; } void add_prime_list_t(struct prime_list_t** list, long n) { struct prime_list_t* node; if(list == NULL) { abort(); } node = (struct prime_list_t*)malloc(sizeof(struct prime_list_t)); if(node == NULL) { abort(); } node->n = n; node->next = NULL; if(*list == NULL) { *list = node; } else { struct prime_list_t* p; p = *list; while(p->next != NULL) { p = p->next; } p->next = node; } } void free_prime_list_t(struct prime_list_t** list) { struct prime_list_t* node; if(list == NULL) { return; } node = *list; while(node != NULL) { struct prime_list_t* p; p = node; node = node->next; free(p); } *list = NULL; } long count_prime_list_t(struct prime_list_t* list) { long c; struct prime_list_t* p; for(p = list, c = 0; p != NULL; p = p->next, c++) ; return c; } long last_prime_list_t(struct prime_list_t* list) { long n; struct prime_list_t* p; n = 0; p = list; while(p->next != NULL) { p = p->next; } return p->n; }
这将是输出：
$kpwr 148933 numbers largest prime 1999993 sum: 142913828922 $
作为参考（如果你在这里，那么你已经在尝试查找答案），我引用Lucy_Hedgehog （在PE的开发团队中）：
这是一种比Eratosthenes筛更有效的解决方案。 它源自用于计算素数的类似算法。 优点是没有必要找到所有素数来找到它们的总和。
主要思想如下：设S（v，m）为2..v范围内的整数之和，它们在筛选后所有质数小于或小于m时保留。 也就是说，S（v，m）是直到v的整数之和，它们是素数或素数大于m的乘积。
如果p不是素数或者v小于p * p，则S（v，p）等于S（v，p-1）。 否则（p prime，p * p <= v）S（v，p）可以通过找到在用p筛选时去除的整数之和从S（v，p-1）计算。 如果它是p与另一个没有小于p的除数的整数的乘积，则在此步骤中删除整数。 这可以表示为
$ S（v，p）= S（v，p-1） – p（S（v / p，p-1） – S（p-1，p-1））。$
动态编程可用于实现此目的。 对于所有正整数v计算S（v，p）就足够了，对于某些整数k和所有$ p \ leq \ sqrt v $，可以表示为floor（n / k）。
def P10(n): r = int(n**0.5) assert r*r <= n and (r+1)**2 > n V = [n//i for i in range(1,r+1)] V += list(range(V[-1]-1,0,-1)) S = {i:i*(i+1)//2-1 for i in V} for p in range(2,r+1): if S[p] > S[p-1]: # p is prime sp = S[p-1] # sum of primes smaller than p p2 = p*p for v in V: if v < p2: break S[v] -= p*(S[v//p] - sp) return S[n]该算法的复杂性约为$ O（n ^ {0.75}）$，需要9 ms才能找到解决方案。
这些想法与寻找总和相似，是Dirichlet双曲线方法的应用。
如果你可以处理2的case测试然后从3开始循环并把i+=2而不是i++减少循环迭代一半