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

Question

I have designed an algorithm which takes an input and checks whether a number is prime or not. Is this correct?

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

Yes you are correct:

Here is a better worded 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

There is an algorithm called Sieve of Eratosthenes for finding prime number upto n number. Asymptotic complexity is O(nlog(logn)).

The pseudo code is something like:

1. Create an array from 0..max
2. Starting at 2, delete every multiple of 2 from the array.
3. Then, go back to the beginning, and delete every multiple of 3.
4. Repeat this starting from the next available number at the beginning of the array.
5. Do this until the square of number you are checking is greater than your max number.
6. Finally, compact the original array.

This array will then contain only the prime numbers up to your max number. You'll find that it's really, really efficient. So efficient that you can use it as a helper method to determine whether or not a number is prime. Want to know if the number 105557 is prime? Only takes 66 steps.

Ruby Code:

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

To check whether a number is prime or not:

def prime?(num)
  sieve(num).include?(num)
end