我正在尝试做一个Project Euler问题。
我正在寻找2,000,000以下所有素数的总和。
这就是我的……
int main(int argc, char *argv[]) { unsigned long int sum = 0; for (unsigned long int i = 0; i %lun", 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 %ldr", 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: %I64dn", 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++
减少循环迭代一半
需要了解更多c/c++开发分享需要帮助优化算法 – 所有素数的总和低于200万,也可以关注C/ C++技术分享栏目---计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享需要帮助优化算法 – 所有素数的总和低于200万相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/979185.html