Как проверить, является ли число простым или нет (Алгоритм с использованием грубой силы)

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-код:

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. Затем вернитесь в начало и удалите все несколько из них.
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