如何檢查數字是否爲素數（使用蠻力的算法）

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

是的，你是正確的：

這是一個更好的措辭psedo-code：

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

有一個叫Sieve of Eratosthenes尋找素數高達n號上午算法。漸近複雜度爲O（nlog（logn））。

的僞代碼是一樣的東西：

1. 創建一個從0..MAX
2. 在2開始的數組，從數組中刪除的2每多。
3. 然後回到開始處，刪除3的每一個倍數。
4. 從數組開頭處的下一個可用數字開始重複此操作。
5. 做到這一點，直到您檢查的數字的平方大於您的最大數量。
6. 最後，緊湊的原始數組。

此數組將只包含素數達到您的最大數。你會發現它確實非常有效。非常高效，您可以將其用作輔助方法來確定數字是否爲素數。想知道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