如何检查一个数是否为素数（使用蛮力的算法）

Question

我设计了一种算法，它接受输入并检查数字是否为质数。这个对吗？

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

Answer 1

有一种名为 Sieve of Eratosthenes 的算法，用于查找最多 n 个数的质数。渐近复杂度为 O(nlog(logn)).

伪代码是这样的：

Create an array from 0..max

Starting at 2, delete every multiple of 2 from the array.

Then, go back to the beginning, and delete every multiple of 3.

Repeat this starting from the next available number at the beginning of the array.

Do this until the square of number you are checking is greater than your max number.

Finally, compact the original array.

此数组将仅包含不超过您的最大数量的质数。你会发现它真的非常有效。如此高效以至于您可以将它用作辅助方法来确定数字是否为质数。想知道数字 105557 是否是质数？只需要66步。

Ruby代码：

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

Answer 2

是的，你是对的：

这是一个更好的措辞伪代码:

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

如何检查一个数是否为素数（使用蛮力的算法）

How to check whether a number is prime or not (Algorithm using brute force)

algorithm

pseudocode

cs50

mit-scratch