Determine if a Number is Prime
Learn to use a loop to find out if a given number is prime.
What are prime numbers?
A prime number is a natural number greater than 1 and is divisible by only 1 and itself.
In other words, a prime number is a positive integer greater than 1 with exactly two factors, 1 and the number itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and so forth.
Note: The number 1 is neither prime nor composite. All other numbers, except for 1, are classified as either prime or composite numbers.
Problem statement
Assume that you have a positive integer n greater than one, and you want to find out if it is prime.
The main steps in problem-solving
Understand the problem
Read the problem statement carefully. The desired output should be “prime” if n is prime and “not prime” otherwise.
Come up with a practical solution
Recall the definition of a prime number. A prime number is not divisible by any other number except itself and 1. Hence, one possible way to check if n is prime is to ensure that it is not divisible by any number from 2 up to n / 2 (if n / 2 is a decimal number, then round it down to the nearest integer).
For example, to check if 11 is a prime number, we divide it by 2, 3, 4, and 5 and see if the remainder is zero. Since none of the given numbers (2, 3, 4, and 5) divide 11 exactly, it is a prime number with only 1 and 11 factors.
Implement your solution
Execute the solution on different test cases. For instance, 5 is prime, and the method above gives the correct answer.
Pseudocode
INPUT n
i = 2
answer = prime
WHILE i <= n / 2
rem = n % i
IF rem is not equal to 0
i = i + 1
ELSE
answer = not prime
END WHILE LOOP
OUTPUT answer
Explanation
We take n
as an input. Then, we set i
to 2, and answer
to “prime”. The code inside the WHILE block runs until i
exceeds n / 2
. Remember that n / 2
is rounded down to the nearest integer. Inside the WHILE block:
-
Set
rem
ton % i
, i.e., the remainder of the division ofn
byi
. -
Then, we check if
rem
is not equal to 0, i.e., ifn
is not divisible byi
. Ifrem
is non-zero, we incrementi
to repeat the same process for the new value ofi
. -
Otherwise, we set
answer
to “not prime” sincen
has a divisor other than 1 and itself. Thus, it is not a prime number. We also break out of the loop usingEND WHILE LOOP
since there is no need to keep checking ifn
is divisible by any other number.
Finally, we output answer
.
Enter a number n between 4 and 100 (both values inclusive) and press the Done button to see the value of i as we enter the WHILE loop and how the values of rem and answer change inside the WHILE block:
Flowchart
Explanation
We use the start symbol to mark the start of the program. Next, we ask for n
using the input symbol. We set the initial values for i
and answer
as shown by the process symbol. Then, we show the possible directions we can go depending on the answer to “is i <= n / 2
?” Remember that n / 2
is rounded down to the nearest integer if it is a decimal.
If i
is less than or equal to n / 2
, we set rem
to the remainder of the division of n
by i
. Then, we check if rem
is not equal to 0. If it is non-zero, we increment i
by 1, as shown in the process symbol. Then, we go back to checking “is i <= n - 1
?” Otherwise, we set answer
to “not prime” and exit the loop.
If i
is greater than n / 2
, then the loop terminates. We use the output symbol to output the answer. Finally, the end symbol marks the end of the program.