[存疑]素数序列

[nesteiner]

版本1 埃氏筛，未解决递归问题

以前用过Clojure写埃氏筛来实现无限素数序列

(defn divisible? [a b]
    (zero? (mod a b)))
(defn sieve [stream]
  (lazy-seq
   (cons (first stream)
         (sieve (filter #(not (divsible? % (first stream)))
                        (rest stream))))))
(def primes (sieve (iterate inc 2)))                    

我打算把这个移到Julia上，说明慢慢补吧，还有很多问题没有解决

struct __Primes end
primes = __Primes() #primes，素数从这个对象中取出

divsible(a,b) = a % b == 0
Base.length(primes::__Primes) = typemax(Int)



# 埃氏筛实现
function sieve(stream) # stream: Iterator
    n = first(stream)
    n,()->sieve(Iterators.filter(x->!divsible(x,n),Iterators.rest(stream,2)))
end

# iterate:
Primes = sieve(Iterators.countfrom(2,1))
function Base.iterate(primes::__Primes)
    Primes
end

function Base.iterate(primes::__Primes,state::T) where T
    state()
end

是否正确？？

julia> collect(Iterators.take(primes,20))
20-element Array{Any,1}:
  2
  3
  5
  7
 11
 13
 17
 19
 23
 29
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

测试性能

julia> @btime collect(Iterators.take(primes,1000))
  2.220 s (3908 allocations: 15.52 MiB)

隔壁的JVM平台测试

euler-project.core> (time (take 1000 primes))
"Elapsed time: 0.030245 msecs"

跑得这么慢肯定有递归问题，慢慢改吧

---

版本2 带缓存(文档随缘吧)

struct __Primes
    dict::Dict{Int,Int}
end
primes = __Primes(Dict{Int,Int}())

function Base.iterate(primes::__Primes)
    primes.dict[1] = 2
    2,(3,2)
end

divsible(a,b) = a % b == 0
function Base.iterate(primes::__Primes,(wait_prime,n)::T) where T
    if n in keys(primes.dict)
        primes.dict[n],(primes.dict[n]+1,n+1)
    elseif any(x->divsible(wait_prime,x),Iterators.filter(y->y<=sqrt(wait_prime),values(primes.dict)))
        iterate(primes,(wait_prime+1,n))
    else
        primes.dict[n] = wait_prime
        wait_prime,(wait_prime+1,n+1)
    end
end

Base.length(primes::__Primes) = typemax(Int)

测试

julia> @btime collect(Iterators.take(primes,1000))
  26.519 μs (905 allocations: 22.08 KiB)

---

[提示]

取几十万的数有点难度，要话几十分钟，隔壁的fib倒是挺快