12345678910111213141516171819202122232425262728293031 |
- #!/usr/bin/ruby
- # Generate all the Carmichael numbers, up to a given bound.
- func carmichael_upto(n) {
- var C = Set()
- 3 .. idiv(1+isqrt(8*n + 1), 4) -> each_prime {|p|
- var t = p*(p-1)
- var c = (p + 2*t)
- loop {
- C << c if c.is_carmichael
- c += t
- break if (c > n)
- }
- }
- return C.sort
- }
- var C = carmichael_upto(1e6)
- say C
- say C.len
- __END__
- [561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633]
- 43
|