-3

入力を受け取り、数値が素数かどうかをチェックするアルゴリズムを設計しました。これは正しいです？

1)Input num
    2)counter= num-1
    3)repeat 
    4)remainder = num%counter
    5)if rem=0 then
    6)broadcast not a prime.no and stop
    7)decrement counter by 1
    8)until counter = 1
    9)say its a prime and stop
4

2 に答える 2

3

はい。それで合っています：

これは、より適切な表現の疑似コードです。

get Num from user
get IsPrime = True
for PFactor ranges from 2 to Num-1 do
  begin block
     if Num divisible by PFactor then set IsPrime = False
  end block
if IsPrime = True then display Num is prime
else display Num is not prime
于 2016-10-06T10:46:42.380 に答える
2

数までの素数を見つけるためのエラトステネスの篩と呼ばれるアルゴリズムがありますn。漸近的な複雑さはO(nlog(logn))です。

擬似コードは次のようなものです。

  1. 0..max から配列を作成する
  2. 2 から始めて、2 の倍数ごとに配列から削除します。
  3. 次に、最初に戻り、3 の倍数ごとに削除します。
  4. 配列の先頭にある次の使用可能な番号から開始して、これを繰り返します。
  5. チェックしている数の二乗が最大数よりも大きくなるまでこれを行います。
  6. 最後に、元の配列を圧縮します。

この配列には、最大数までの素数のみが含まれます。本当に効率的であることがわかります。非常に効率的であるため、数値が素数かどうかを判断するヘルパー メソッドとして使用できます。105557 が素数かどうか知りたいですか? わずか66歩。

ルビーコード:

def sieve(max)
  # Set up an array with all the numbers from 0 to the max
  primes = (0..max).to_a

  # Set both the first and second positions (i.e., 0 and 1) to nil, as they
  # aren't prime.
  primes[0] = primes[1] = nil

  # Iterate through primes array
  counter = 0
  primes.each do |p|
    # Skip if nil
    next unless p

    # Break if we are past the square root of the max value 
    break if p*p > max
    counter += 1
    # Start at the square of the current number, and step through.
    # Go up to the max value, by multiples of the current number, and replace
    # that value with nil in the primes array
    (p*p).step(max,p) { |m| primes[m] = nil }
  end

  # Finally, return the compacted array.
  puts "Solved for #{max} in #{counter} steps."
  primes.compact
end

数値が素数かどうかを確認するには:

def prime?(num)
  sieve(num).include?(num)
end
于 2016-10-05T21:04:41.823 に答える