33 lines
1.2 KiB
Ruby
33 lines
1.2 KiB
Ruby
def prime?(n) # P3 Prime Generator primality test
|
|
return n | 1 == 3 if n < 5 # n: 2,3|true; 0,1,4|false
|
|
return false if n.gcd(6) != 1 # this filters out 2/3 of all integers
|
|
pc, sqrtn = 5, Integer.sqrt(n) # first P3 prime candidates sequence value
|
|
until pc > sqrtn
|
|
return false if n % pc == 0 || n % (pc + 2) == 0 # if n is composite
|
|
pc += 6 # 1st prime candidate for next residues group
|
|
end
|
|
true
|
|
end
|
|
|
|
def divisors(n) # divisors of n -> [1,..,n]
|
|
f = []
|
|
(1..Integer.sqrt(n)).each { |i| (n % i).zero? && (f << i; f << n / i if n / i != i) }
|
|
f.sort
|
|
end
|
|
|
|
# The smallest divisor d of p-1 such that 10^d = 1 (mod p),
|
|
# is the length of the period of the decimal expansion of 1/p.
|
|
def long_prime?(p)
|
|
return false unless prime? p
|
|
divisors(p - 1).each { |d| return d == (p - 1) if 10.pow(d, p) == 1 }
|
|
false
|
|
end
|
|
|
|
start = Time.now
|
|
puts "Long primes ≤ 500:"
|
|
(7..500).each { |pc| print "#{pc} " if long_prime? pc }
|
|
puts
|
|
[500, 1000, 2000, 4000, 8000, 16000, 32000, 64000].each do |n|
|
|
puts "Number of long primes ≤ #{n}: #{(7..n).count { |pc| long_prime? pc }}"
|
|
end
|
|
puts "\nTime: #{(Time.now - start)} secs"
|