This post has already been read 2517 times!

# Introduction

Each **natural number** that is **divisible** only by **1 and itself** is **prime**.

**Prime numbers** appear to be more interesting to humans than other numbers.

Why is that and why prime numbers are more important than the numbers that are divisible by 2, for instance ?

Perhaps the answer is that prime numbers are largely used in cryptography, although they were interesting for the ancient Egyptians and Greeks (Euclid has proved that the prime numbers are infinite circa 300 BC).

The problem is that there is not a formula that can tell us which is the next prime number, although there are algorithms that check whether a given natural number is prime. It’s very important these algorithms to be very effective, especially for big numbers.

# Overview

As I said each natural number that is divisible only by 1 and itself is prime. That means that 2 is the first prime number and 1 is not considered prime. It’s easy to say that 2, 3, 5 and 7 are prime numbers, but what about 983? Well, yes 983 is prime, but how do we check that?

If we want to know whether n is prime the very basic approach is to check every single number between 2 and n. It’s kind of a brute force.

# Implementation

Beside that these implementations shows how we can find prime number,

they are a very good example of how an algorithm can be optimized a lot with some small changes.