Determine primality

Question

put "enter a number to determine if it is or is not prime"
get primenum
% for i : 1 .. primenum by 1
% end for
if (primenum / primenum) = 1 or primenum / 1 = 0 then
    put primenum, " is a prime number"
else
    put primenum, " is not a prime number"
end if

Output says that 12 is a prime number, and that's wrong. How can I fix this code?

Answer 1

Your code ... doesn't make a lot of sense.

% for i : 1 .. primenum by 1
% end for

Wooh. Empty loop. Doesn't do anything except burn clock cycles.

if (primenum mod primenum) = 0

Will always be true.

Also, you've got your condition the wrong way around. If it is divisible by something (other than itself and 1), then it is not prime.

The solution? Probably rewrite it in psuedocode and then turn that into real code, rather than trying to hack up something without understanding it at all.

Answer 2

Well, I don't know that language, but it looks to be fairly easy to read. Your first problem is this line:

if (primenum / primenum) = 1 or primenum / 1 = 0 then

This is testing to see if primenum divided by primenum is one or if primenum divided by one is zero. The first condition will always be true and thus your algorithm will report that every integer is a prime number.

Let's recall the definition of a prime number. A natural number n is prime if it has exactly two distinct natural number divisors. This means that to check and see if n is prime you must validate that there are no other divisors of n except for 1 and n itself (note that implicitly n can not be equal to 1 otherwise its only divisors are 1 and 1 which are not distinct). To do this, just consider all possible numbers that could be divisors of n excluding 1 and n itself and check if any of them divide n. This means that we just loop from 2 to n - 1 checking if any of these numbers evenly divide n. The natural numbers in the range 2 to n - 1 are the only possible numbers that could invalidate n from being prime.

Thus, the most naive way to implement a test as to whether a number is prime is following. Accept as input a number n. Then, check to see if n is less than 2. If it is it can not be a prime number. Then, loop from 2 to n - 1; call the loop variable k. Check to see if any k in 2 to n - 1 evenly divides n (if n mod k = 0). If there is such a k, then n can not be prime and you can break from the loop. Otherwise, if the loop terminates without breaking then n is prime. So, in pseudocode

integer n
get n
boolean flag
if n < 2
    flag = false
else
    flag = true
    for k = 2 to n - 1
        if n mod k = 0 
            flag = false
            break
if flag
    print "prime"
else
    print "not prime"

Now, just one minor comment about your code. Don't name the input primenum. A reader of your code might that think that primenum is in fact a prime number because you named it so. A name like valueToTest would be strongly preferred here.

Answer 3

The defining property of a prime is not that it is divisible by 1 and itself (all number have those properties), but that it is not divisible by anything else.

Try working from there.

Answer 4

1st trick of prime number is don't go past the square root of the number.