123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566 |
- #!/usr/bin/julia
- # Daniel "Trizen" Șuteu
- # Date: 16 November 2021
- # https://github.com/trizen
- # https://projecteuler.net/problem=133
- # Runtime: 1.137s
- using Primes
- function divisors(n)
- d = Int64[1]
- for (p,e) in factor(n)
- t = Int64[]
- r = 1
- for i in 1:e
- r *= p
- for u in d
- push!(t, u*r)
- end
- end
- append!(d, t)
- end
- return sort(d)
- end
- function prime_znorder(a, n)
- for d in divisors(n-1)
- if (powermod(a, d, n) == 1)
- return d
- end
- end
- end
- function p_133()
- factors = Dict{Int64, Nothing}()
- limit = 100_000
- N = 10^floor(Int64, log2(big(limit)))
- for p in primes(7, limit)
- if (rem(N, prime_znorder(10, p)) == 0)
- factors[p] = nothing
- end
- end
- total = 0
- for p in primes(limit)
- if !haskey(factors, p)
- total += p
- end
- end
- return total
- end
- println(p_133())
|