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 to n % i, i.e., the remainder of the division of n by i.

  • Then, we check if rem is not equal to 0, i.e., if n is not divisible by i. If rem is non-zero, we increment i to repeat the same process for the new value of i.

  • Otherwise, we set answer to “not prime” since n has a divisor other than 1 and itself. Thus, it is not a prime number. We also break out of the loop using END WHILE LOOP since there is no need to keep checking if n 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.