lion137
2018-12-13 17:50

Sito Erastotenesa

Było coś obiecane z nowej książk i jest. Najpierw kod:

#include <iostream>
#include <vector>
#include <iterator>
#include <cctype>

#define RandomAccessIterator typename
#define Integer typename

template <RandomAccessIterator I, Integer N>
void mark_array(I first, I last, N factor) {
    first = false;
    while (last - first > factor) {
        first = first + factor;
        *first = false;
    }
}

template <RandomAccessIterator I, Integer N>
void erastosthenes_sieve(I first, N n) {
    I last = first + n;
    std::fill(first, last, true);
    N i(0);
    N index_square(3);
    N factor(3);
    while (index_square < n) {
        if (first[i]) {
            mark_sieve(first + index_square, last, factor);
        }
        ++i;
        index_square += factor;
        factor += N(2);
        index_square += factor;
    }
}

Szkoda, że nie można sobie już definiować konceptów / pojęć? Tylko takie haki preprocesorem, ale każdy się chyba domyśli, jaki typ dać w miejsce Integer:). Jak widać nie ma nigdzie tablicy z wartościami liczb pierwszych, nie potrzeba, można je sobie wyciągnąć z mutowanej(void) w sicie tablicy, generalnie czegokolwiek, na co będzie wskazywał Iterator(true jest na 2i + 3 miejscu).

std::vector<int> primes;
primes.push_back(2); // dodanie dwójki
    for (int i = 0; i < vec1.size(); i++){ // vec1 - wektor "wysłany" do sita 
        if (it1[i]){ // wskazuje na vec1
            primes.push_back(2 * i + 3);
        }
    }

W miarę szybkie (milion liczb pierwszych w 0.1 sek.), do matematyki rekreacyjnej i na uczelnię wystarczy:)
#theory #computation #primes

Pijak

Kolejna dawka szit kodu, to się szanuje :)

lion137

Dziękujemy za kolejny merytoryczny komentarz xD

Afish

A nie lepiej zrobić typename RandomAccessIterator zamiast bawić się preprocesorem? Robienie typów o jednoliterowej nazwie nie jest fajne.

lion137

Myślałem o tym, ale chciałem zanęcić trochę concepts, które mają się pojawić niedługo:)