素数を見つけ出すプログラムを作ってみた

処理速度を向上させていくのを身で感じた

暇だったんで、なんとな～く素数をプロットするプログラムをRubyで組んでみた。

まず、ただ単に数字に対してその数字以下の数字で割れたら素数じゃない、割れなかったら素数という総当たり戦でやりました。
結果・・・1万くらいまでは数秒で出せるけど5万くらいからちょっときつい

次に、割り切れるのか判断している途中でもう素数じゃないってわかったら次の数に進むように改良してみた。
結果・・・100万くらいまで出力可能になった

最後に、数学の知識を使って調べる数の平方根以下の範囲でのみ調べるように書き換えてみた。
結果・・・1000万くらいまで数秒で出力可能で、1億までは頑張れば出力できるようになった。

こんな感じですごいプログラムの成長を感じる取り組みやった。

P.S.暇すぎて因数分解の機能まで作った

実際のコード

def allprime (max) #素数の羅列表示
    #変数初期化
    prime_number = [2]
    number = 3
    ins = 0
    #繰り返し処理
    (max - 2).times do
        answer = "true"
        insmax = (number ** (1/2.0)).ceil #平方根計算
        prime_number.each do |i|
            ins = number % i
            if ins == 0 #割り切れるか判断
                answer = "false"
                break
            elsif i > insmax
                break
            end
        end

        if answer == "true"
            prime_number.push(number)
        end
        number += 1
    end
    prime_number
end

def factorization (number)
    factorizated_hash = {}
    prime_number_array = allprime (number)
    prime_number_array.each do |i|
        if number % i == 0
            index = 0
            while number % i == 0 do
                number /= i
                index += 1
            end
            factorizated_hash.store(i.to_s, index)
        end
        break if number == 1

    end
    factorizated_hash
end

#main
puts ("どのツールを使用しますか？")
puts ("すべての素数を表示　-> 1")
puts ("因数分解　-> 2")
tools = gets.to_i
case tools
when 1
    print ("どこまでの素数を表示しますか？")
    input = gets.to_i
    output = allprime(input)
    p output
    puts ("計：" + output.size.to_s)
    puts ("処理完了")
when 2
    print ("因数分解する数字：")
    input = gets.to_i
    output = factorization (input)
    output.each do |key, value|
        puts (key.to_s + "^" + value.to_s)
    end
    puts ()
    puts ("処理完了")
end