Tociyuki::Diary

■[Ruby]素数判定と原始根判定による 292 までのクノー数

ある整数がクノー数かどうかを、昨日はツイスト置換を巡回因子分解して判定するコードを書きました。動作は遅く、2 から 292 までの整数からクノー数を選び出すのに、一呼吸ほどの間が開きます。それに対して、素数判定と原始根判定を組み合わせてやると、すばやく判定することができるようになります。2 または -2 が原始根かどうか判定するための位数計算を富豪的におこなっているものの、これでも、巡回因子分解するより高速です。

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-

PRIME_NUMBER_SIEVE = Array.new(1000 + 1, true).tap do |sieve|
  sup = Math::sqrt(1000).to_i
  sieve[0] = sieve[1] = false
  (2 ... sup).each do |c|
    0.step(sieve.size, c) do |i|
      if i != c
        sieve[i] = false
      end
    end
  end
end

def prime?(n)
  n <= 1000 or raise ArgumentError, 'Out of sieve.'
  PRIME_NUMBER_SIEVE[n]
end

def order(n, q)
  c = 1
  a = n
  while a != 1
    a = (a * n) % q
    c += 1
  end
  c
end

def queneau_number?(n)
  q = n * 2 + 1
  return false if ! prime?(q)
  order(2, q) == q - 1 || order(q - 2, q) == q - 1
end

def queneau_numbers(n)
  [].tap{|a|
    (2 .. n).each do |i|
      if queneau_number?(i)
        a << i
      end
    end
  }
end

if $0 == __FILE__
p queneau_numbers(292)
#=> [
#    2, 3, 5, 6, 9, 11, 14, 18, 23, 26, 29, 30, 33, 35, 39, 41, 50, 51,
#    53, 65, 69, 74, 81, 83, 86, 89, 90, 95, 98, 99, 105, 113, 119, 131,
#    134, 135, 146, 155, 158, 173, 174, 179, 183, 186, 189, 191, 194,
#    209, 210, 221, 230, 231, 233, 239, 243, 245, 251, 254, 261, 270,
#    273, 278, 281,
# ]
end

Permalink | コメント(0) | トラックバック(0) | 18:36