JuliaMath / JuliaMath/Primes.jl

possible number theory functions to add

Open
#122 6 comments 0 reactions 0 assignees View on GitHub
Dominant language
Julia
Stars
108
Forks
34
PR merge metrics
No merged PRs in 30d

Description

Here is a example of two number theory functions made fast by `eachfactor`

```
"""
`prime_residues(n)` the numbers less than `n` and prime to `n`

julia> [prime_residues(24)]
1-element Vector{Vector{Int64}}:
[1, 5, 7, 11, 13, 17, 19, 23]
"""
function prime_residues(n)
if n==1 return [0] end
pp=trues(n) # use a sieve to go fast
for (p,np) in eachfactor(n)
pp[p:p:n].=false
end
(1:n)[pp]
end

"""
`divisors(n)` the increasing list of divisors of `n`.

julia> [divisors(24)]
1-element Vector{Vector{Int64}}:
[1, 2, 3, 4, 6, 8, 12, 24]
"""
function divisors(n::Integer)::Vector{Int}
sort(vec(map(prod,Iterators.product((p.^(0:m) for (p,m) in eachfactor(n))...))))
end

```

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.