AP1 2017-12-01 Garbell d'Eratòstenes

p1.cc

// Programa per trobar tots els primers entre 0 i n.
// Implementació amb n+1 crides a es_primer()

#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

double now() {
    return clock() / double(CLOCKS_PER_SEC);
}

bool es_primer(int x) {
    if (x <= 1) return false;
    for (int d = 2; d*d <= x; ++d) {
        if (x%d == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;

    double t1 = now();
    vector<bool> p(n+1);
    for (int i = 0; i <= n; ++i) {
        p[i] = es_primer(i);
    }
    double t2 = now();

    for (int i = 0; i <= n; ++i) if (p[i]) cout << i << endl;
    cout << endl << t2 - t1 << endl;
}

p2.cc

// Programa per trobar tots els primers entre 0 i n.
// Implementació amb Garbell d'Erastòtones

#include <iostream>
#include <vector>
#include <ctime>
using namespace std;

double now() {
    return clock() / double(CLOCKS_PER_SEC);
}

int main() {
    int n;
    cin >> n;

    double t1 = now();
    vector<bool> p(n+1, true);
    p[0] = p[1] = false;
    for (int i = 2; i*i <= n; ++i) {
        if (p[i]) {
            for (int j = i+i; j <= n; j += i) {
                p[j] = false;
            }
        }
    }
    double t2 = now();

    for (int i = 0; i <= n; ++i) if (p[i]) cout << i << endl;
    cout << endl << t2 - t1 << endl;
}

A classe no he fet bé la mesura dels temps. 😪

Amb n = 10000000, el p1 em triga 4.032 segons, en canvi p2 triga 0.027 segons. Amb això comprovem que a la pràctica Eratòstenes és més eficient! 👍

Proveu-ho al vostre ordinador! 🖥️