What are prime numbers:

prime numbers are natural numbers (1,2,…) that are divisible by exactly 2 different natural numbers:

Exception: 0 is not a prime number

example

When you use prime numbers:

– in encryption (example of the RSA algorithm)

recognize prime numbers

how to make a program that can recognize prime numbers?

We should check all the variables that have only one option to factorize into natural numbers. As shown in the example. You can get 3 only by multiplying 1 and 3. There are not more options therefore 3 is a prime number.

Comparing the numbers 5 and 6. 5 is prime number and 6 is not

• 5 * 1 is the only option
• 6 * 1 and 2 *3  and 3*2 are 3 options

Maybe you see the pattern now, for prime numbers, there is only one number in the row which has no remainder: dividing by number 1.

For NOT prime numbers there are more numbers.

A commonly used way of returning the remainders is using the modulo/modules operator.

Steps:

1. So first you should take out the possibilities of dividing by 0 and 1

• division of a number by 0 is not allowed in maths
• division of a number by 1 this is always a number without a remainder

2. then, look if there are more occurrences of cases in which the remainder is 0. Because if there are more cases. You know it is NO prime number

java example

package PrimeNumbers;

public class RecognizePrimeNumbers {
	
	
	boolean isPrime(int number) {
		if (number == 0 || number == 1) {
			return false;
		}
		for (int i=2; i<=number-1; i++) {
			if (number%i == 0) {
				return false;
			}
		}
		
		return true;
	}
	
	void start() {
		boolean result = isPrime(5);
		System.out.println(result);
		
	}

	public static void main(String[] args) {
		new RecognizePrimeNumbers().start();
	}

}

java example more efficient

So, this could be your final solution. It works. However, we can make it more efficient. Because, if we think about it mathematically, there will something happen over time. For example, take the number 16:

• 16/1=16
• 16/2 =8
• 16/3=5.333
• 16/4=4
• 16/5=3.2
• 16/6=2.67
• 16/7=2.28
• 16/8=2
• 16/9=1.77
• 16/10=1.6
• 16/11=1.45
• 16/12=1.33
• 16/13=1.23
• 16/14=1.14
• 16/15=1.06

As you can see after it crosses the median value it will always have a remainder. This holds for every number. Therefore, we can say that our program only has to loop until a certain point.

package PrimeNumbers;

public class RecognizePrimeNumbers {
	
	
	boolean isPrime(int number) {
		int m = number/2;
		
		if (number == 0 || number == 1) {
			return false;
		}
		for (int i=2; i<=m; i++) {
			if (number%i == 0) {
				return false;
			}
		}
		
		return true;
	}
	
	void start() {
		boolean result = isPrime(5);
		System.out.println(result);
		
	}

	public static void main(String[] args) {
		new RecognizePrimeNumbers().start();
	}

}