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

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

是的，你是对的：

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

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

Answer 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