Нужна помощь в оптимизации алгоритма - сумма всех простых чисел до двух миллионов

Question

Я пытаюсь задать Project Euler вопрос.

Я ищу сумму всех простых чисел меньше 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, как в вопросе.

Я предполагаю, что есть какой-то алгоритм, который может сократить объем работы. Проблема в том, что я не знаю, что это.

Может кто-нибудь указать мне правильное направление?

Спасибо.

Answer 1

С i от 2 до 2000000 (или любым другим верхним пределом), когда вы определите, что i - простое число, вы знаете, что {2i, 3i, 4i, ..., ni} не являются простыми числами, где ni <= 2000000.

Вам не нужно проверять эти числа - вы знаете, что они не простые.

По мере прохождения массива testNumbers и исключения чисел из этого списка числа, которые вы теперь знаете, не являются простыми, вы значительно сокращаете числа, которые вам действительно нужно проверить.

Да, это Сито Эратосфена.

Answer 2

Вы можете ускорить вашу функцию isPrime(int num), передав массив простых чисел, обнаруженных до сих пор, и проверьте, является ли num кратным этим простым.Также вам не нужно зацикливаться до num, только sqrt(num).

Answer 3

вы можете сократить время поиска простого числа. Есть миллион способов сделать это. Я думаю, вам не нужно тестировать до num, а только до sqrt (num), но это только немного вам поможет (по фактическим простым числам)

Существуют статистические методы проверки того, является ли простое число на самом деле простым, которые быстрее и могут быть ошибочными только один раз за 2 ^ много ....

Самый быстрый способ найти простое число был найден исследователем из Индии, но я не могу найти ссылку.

Вы также можете посмотреть здесь:

Wiki

Answer 4

Для справки (если вы здесь, значит, вы уже пытаетесь найти ответ), я цитирую Lucy_Hedgehog (в команде разработчиков для PE):

Вот решение, которое более эффективно, чем сито Эратосфена.Он получен из аналогичных алгоритмов для подсчета простых чисел .Преимущество состоит в том, что нет необходимости находить все простые числа, чтобы найти их сумму.

Основная идея заключается в следующем: пусть S (v, m) будет суммой целых чисел в диапазоне 2..vкоторые остаются после просеивания со всеми простыми числами, меньшими или равными m.То есть S (v, m) - это сумма целых чисел до v, которые либо просты, либо являются произведением простых чисел, больших m.

S (v, p) равно S (v, p-1), если p не простое число или v меньше p * p.В противном случае (p prime, p * p <= v) S (v, p) может быть вычислено из S (v, p-1) путем нахождения суммы целых чисел, которые удаляются при просеивании с помощью p.На этом этапе удаляется целое число, если оно является произведением p на другое целое число, у которого нет делителя, меньшего, чем p.Это может быть выражено как </p>

$ S (v, p) = S (v, p-1) - p (S (v / p, p-1) - S (p-1, p-1)). $

Для этого можно использовать динамическое программирование.Достаточно вычислить S (v, p) для всех натуральных чисел v, которые представляются в виде floor (n / k) для некоторого целого числа k и всех $ p \ leq \ sqrt v $.

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 мс.

Идеи аналогичны нахождению суммы иявляется приложением метода гиперболы Дирихле .

Answer 5

, если вы можете обработать case тест для 2, тогда начните цикл с трех и поставьте i+=2 вместо i++, уменьшив итерацию цикла наполовину

Answer 6

#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

$

Answer 7

Подсказка: Используйте BitArray и метод seive.

См. Код , если вы не можете его выяснить. Код написан на Java, но его не сложно перевести на C.

Answer 8

Используйте сито Atkin, его оптимизированная версия сита Эратосфена ссылка .