12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 |
- #!/usr/bin/julia
- # Generate squarefree k-almost primes in range [A,B].
- # See also:
- # https://en.wikipedia.org/wiki/Almost_prime
- using Primes
- const BIG = false # true to use big integers
- function big_prod(arr)
- BIG || return prod(arr)
- r = big"1"
- for n in (arr)
- r *= n
- end
- return r
- end
- function squarefree_almost_primes_in_range(A, B, n::Int64)
- A = max(A, big_prod(primes(prime(n))))
- F = function(m, lo::Int64, j::Int64)
- lst = []
- hi = round(Int64, fld(B, m)^(1/j))
- if (lo > hi)
- return lst
- end
- if (j == 1)
- lo = round(Int64, max(lo, cld(A, m)))
- if (lo > hi)
- return lst
- end
- for q in (primes(lo, hi))
- push!(lst, m*q)
- end
- else
- for q in (primes(lo, hi))
- lst = vcat(lst, F(m*q, q+1, j-1))
- end
- end
- return lst
- end
- return sort(F((BIG ? big"1" : 1),2,n))
- end
- # Generate squarefree 5-almost in the range [3000, 10000]
- k = 5
- from = 3000
- upto = 10000
- println(squarefree_almost_primes_in_range(from, upto, k))
|