Генерация n простых чисел

Question

Нужно ввести число n и сгенерировать n простых чисел. Есть ли какой-нибудь алгоритм для этого? Нашел только решето Эратосфена, но оно не подходит для моего задания.

Answer 1

вот

from itertools import islice



def primes():
    if hasattr(primes, "D"):
        D = primes.D
    else:
        primes.D = D = {}

    def pr():
        q = 2
        while True:
            if q not in D:
                yield q
                D[q * q] = [q]
            else:
                for p in D[q]:
                    D.setdefault(p + q, []).append(p)
                del D[q]
            q += 1
    return pr()


n = int(input())
spisok = list(islice(primes(), 0, n))

Answer 2

Простейший вариант на С++:

bool is_prime(int k)
{
    for(int i = 3; i*i <= k; i+= 2)
        if (k%i == 0) return false;
    return true;
}

vector<int> primes(int n)
{
    vector<int> v;
    if (n >= 1) v.push_back(2);
    for(int k = 3; v.size() < n; k += 2)
        if (is_prime(k)) v.push_back(k);
    return v;
}

Вот через решето Эратосфена, просто с запасом сверху. Его можно и уменьшить...

vector<int> eratos(int n)
{
    vector<int> r;
    if (n <= 1)
    {
        if (n == 1) r.push_back(2);
        return r;
    }
    int m = (n+6)*(log(n)+log(log(n)));

    vector<int> v(m,1);
    v[0] = v[1] = 0;
    int k = 2;
    while(k*k <= m)
    {
        for(int i = 2*k; i < m; i+=k) v[i] = 0;
        while(v[++k] == 0);
    }
    for(int i = 2; r.size() < n; ++i)
        if (v[i]) r.push_back(i);
    return r;
}

Примерное сравнение времен вычисления для разных n на моей машине

n                 100    1000     10000     100000
primes(), mks       9     170      4500     131000
eratos(), mks      12      54       650       7400

БЛОГ НА HUSL

Генерация n простых чисел

Ответы (2 шт):