素数判断

Question

forループを使った素数判定のアルゴリズムがわからないです。neはnの平方根を超えない最大の整数です。 forループの中は、n を 2 から始まって ne までの数で割った，その余りが 0 であるかどうか を調べます。

n = ARGV[0].to_i
ne = sqrt(n).to_i
pflag = true
for i in 2 .. n
r = n % ne
if r == 0 then
pflag = false
end
end
if pflag then
puts"#{n}は素数です。"
else
puts"#{n}は合成数です。"
end

回答お願いします。

Answer 1

日本語で書いている部分は合ってますので、日本語の通り、プログラムを書いてください。

どこが違っているか分からない場合は、プログラムを日本語に直しながら音読するのが良いかと。
それと質問文の日本語を比べてください。

あと、sqrt(n)は、Math.sqrt(n)ですね。

Answer 2

「forループの中は、n を 2 から始まって ne までの数で割った」とありますので、i の値が 2 から始まって ne で終わるようにプログラムを書き換えてください。その後どうするかは、考えればきっとわかるはずです。

Comments

[退会済みユーザー]

回答ありがとうございます！

n = ARGV[0].to_i
ne = sqrt(n).to_i
pflag = true
for i in 2 .. ne
r = n % ne
if r == 0 then
pflag = false
end
end
if pflag then
puts"#{n}は素数です。"
else
puts"#{n}は合成数です。"
end

これで書きなおして見たんですが、出力できないです。
何が間違っているかわかりません。

[退会済みユーザー]

n = ARGV[0].to_i
ne = sqrt(n).to_i
pflag = true
for i in 2 .. ne
r = n / i
if r == 0 then
pflag = false
end
end
if pflag then
puts"#{n}は素数です。"
else
puts"#{n}は合成数です。"
end

上の様に、n を 2 から始まって ne までの数で割ることを考えましたが、出力できないです。
回答お願いします。

[ozwk]

「出力できない」と「実行できない」は意味合いが違いますが、
どちらでしょうか
もし、sqrtなんてないぞとエラーが出ているのであれば
Math.sqrt()です。

[退会済みユーザー]

include Math
n = ARGV[0].to_i
ne = sqrt(n).to_i
pflag = true
for i in 2 .. ne
if n / i == 0 then
pflag = false
end
end
if pflag then
puts"#{n}は素数です。"
else
puts"#{n}は合成数です。"
end

このように考えたのですが、
実行してみたら、素数と合成数が逆に出てきます。

[tatsuya6502]

あ、先ほどの引用が悪かったですね。「...で割った」ではなくて、原文の「...で割った，その余りが 0 で」で、やってみてください。

Answer 3

すでに解決はしたとおもいますが、コード例を示します。

• 素数判定部分を関数にしました。
• 偶数なら素数ではないことをくみこみました。
• 約数の判定は、奇数だけを試すようにしました。

def prime?(n)
  # 2 は素数
  return true if n == 2
  # 偶数なら素数ではない。
  return false if n % 2 == 0

  # 奇数で割っていく
  3.step(Math.sqrt(n), 2).each do |i|
    return false if n % i == 0
  end
  true
end

n = ARGV[0].to_i
if prime?(n)
  p = '素数'
else
  p = '合成数'
end
puts "#{n}は#{p}です。"