Prime Iterator in Julia

Question

Есть ли (эффективный) итератор для генерации простых чисел в Юлии? Встроенная функция primes[N] генерирует все простые числа до N сразу, а не по мере необходимости, и может не использоваться, когда N очень большой или неизвестный.

Answer 1

Вы можете выбирать счетчик, проходящий через (большой) Интс (The Base.Count{BigInt} итераторов) с помощью тест вероятностного простоты

iterprimes = filter(isprime,countfrom(big(2),1)) 

Тогда, например

julia> collect(take(iterprimes, 5)) 
5-element Array{Any,1}: 
    2 
    3 
    5 
    7 
11 

Это не так эффективно в целом как сито, но не сохраняет огромную структуру в памяти. Я помню, что isprime имеет по крайней мере ложные срабатывания до 2^64 при стандартном выборе повторений.

Edit:

Вторая возможность заключается в том, чтобы генерировать (см Generator) ломти primes(N*(i-1)+1,N*i) и Base.flatten их в один список:

Base.flatten(primes(1000000*(i-1)+1,1000000*i) for i in countfrom(1)) 

На этой машине это итератор на самом деле бьет простой primes для вычисляя первые 10^9 простых чисел.

Edit 2:

итератора с помощью gmpz «s nextprime.

type 
    PrimeIter 
end 
function nextprime(y::BigInt) 
    x = BigInt() 
    ccall((:__gmpz_nextprime,:libgmp), Void, (Ptr{BigInt},Ptr{BigInt}), &x, &y) 
    x 
end 
Base.start(::PrimeIter) = big(2) 
Base.next(::PrimeIter, state) = state, nextprime(state) 
Base.done(::PrimeIter, _) = false 
Base.iteratorsize(::PrimeIter) = Base.IsInfinite() 


> first(drop(PrimeIter(), 10^5)) 
1299721 

Answer 2

Вы можете проверить Lazy.jl, что дает вам максимальную итерацию по требованию. Он работает на неизвестном большом количестве. Предполагается, что вы хотите использовать все простые числа, меньшие, чем верхняя граница, и иметь пространство для их хранения.

Цитата из их ридх: -

# isprime defined in terms of the prime numbers: 
isprime(n) = 
    @>> primes begin 
    takewhile(x -> x<=sqrt(n)) 
    map(x -> n % x == 0) 
    any; ! 
    end 

# the prime numbers defined in terms of isprime: 
primes = filter(isprime, range(2)); 

take(20, primes) 
#> (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71) 

Для объяснения кода, во-первые isprime функции определяются с использованием списка всех простых чисел primes (которые не были определены еще в тот момент времени), по взяв все простые числа меньше квадратного корня из n, проверьте, не делятся ли какие-либо из них n и логически отрицают результат.

Тогда prime определяется как filter из isprime по всем целым числам от 2 до.

Чтобы получить все простые числа ниже n, вы можете просто запустить @>> primes takewhile(p -> p <= n) вместо take.

Answer 3

Один из вариантов, который экономится при хранении, но даст вам несколько простых чисел - использовать колесо, см. Wheel Factorization. Все, что необходимо, - это сохранить последнее найденное число и перейти к следующему номеру на колесе.

Например, обрабатывайте 2 и 3 отдельно. Затем из 5 добавьте 2 и 4 поочередно: 5, 7, 11, 13, 15 ... Результирующий поток чисел устраняет все кратные 2 и 3. Есть более сложные колеса, которые также будут устранять кратные 5 или более простых простых чисел.

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