prime number is a whole number that is greater than 1, and it can be only divided by 1 or itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17… Please note 1 is not a prime number. Given a number n, you can check whether the number is prime by using following methods.

prime numbers

Table of Content


Iteration

This is an intuitive method. We can check every integer from 1 to any number that is smaller than itself. If cannot find a factor, the input is a prime number.

Java

Javascript

Python

Doodle

prime iteration


Iteration better

Due to the symmetry of the factors, the for loop only needs to traverse[2, sqrt (n)]. This improves the time complexity from O(n) to O(sqrt(n)).

Java

Javascript

Python

Doodle

prime iteration better


Recursion

We can also apply the square root to recursion to save the checking time. But due to the call stacks, the space complexity will be O(sqrt(n)) too.

Java

Javascript

Python

Doodle

prime recursion

Download Java, JavaScript and Python code
Prime recursion doodle
Mathematics in software engineering