代码之家 › 专栏 › 技术社区 › alex

需要帮助优化算法-200万以下所有素数之和

alex · 技术社区 · 15 年前

我在找2000000以下的所有素数之和。

这就是我所拥有的。。。

int main(int argc, char *argv[]) {


    unsigned long int sum = 0;

    for (unsigned long int i = 0; i < 2000000; i++) {


        if (isPrime(i)) {
            sum += i;
        }
    }

    printf("sum => %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 就像这个问题。

有人能告诉我正确的方向吗?

谢谢。

8 回复 | 直到 11 年前

Alex Reynolds 15 年前

与 i 从 2 到 2000000 (或任何上限),一旦你确定 我 是质数,你就知道了 {2i, 3i, 4i, ..., ni} ni <= 2000000 .

你不需要测试那些你知道不是质数的数字。

testNumbers 从这个列表中去掉数字,你现在知道的数字不是素数,你就大大减少了你真正需要测试的数字。

是的,这是埃拉托舍内斯的筛子。

Dani 15 年前

你可以缩短寻找素数的时间。有无数种方法可以做到。

有一些统计方法可以检查一个素数是否真的是素数,这种方法速度更快,而且在很多情况下只能被误判一次。。。。

找到质数最快的方法是由一位来自印度的研究人员发现的,但我找不到其中的联系。

Wiki

fastcodejava 15 年前

你可以加快速度 isPrime(int num) num 是这些素数的倍数。你也不需要循环到 号码 sqrt(num) .

LPs 10 年前

如果你能处理好 case 2 然后从3开始循环 i+=2 而不是 i++

srean 15 年前

使用阿特金筛,它是埃拉托申斯筛的优化版本 link .

Emil 15 年前

使用位数组和seive方法。

见 code 如果你搞不懂的话,代码是用Java编写的,但不难翻译成C语言。

Cristian Amarie 13 年前

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

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

$

qwr 7 年前

作为参考(如果您在这里,那么您已经在尝试查找答案),我 quote Lucy_Hedgehog (在体育发展团队中):

这是一个比筛子更有效的解决方案埃拉托舍内斯。它来自于 counting primes 优点是不需要找到所有要找到的素数

主要思想如下:设S(v,m)为也就是S(v,m)是到v的整数和素数或大于m的素数的乘积。

如果p不是素数或v小于p,S(v,p)等于S(v,p-1) 如果整数是p与另一个没有小于p的除数的整数表示为

动态编程可以用来实现这一点。足以计算所有可表示为的正整数v的S(v,p)
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毫秒。找到解决办法。

finding totient sum 并且是 Dirichlet hyperbola method .