# Primality test (naive approach)

Testing number's primality is a quite important task in computer science. For the most part, prime numbers are used in public key cryptography algorithms. Also there are applications for hash tables and pseudorandom numbers generators. There are two types of algorithms to check whether number is prime: deterministic and probabilistic. To tell the truth, there are dozens of primality test algorithms. In current article we are going to develop and discuss the most naive approach, called **trial division**, and its modifications.

## What is a prime number?

**Prime number** is a number, which have exactly two distinct natural number divisors, 1 and itself. The most naive approach to check whether a number is prime is to follow the definition. Algorithm to check number's n primality:

- if number is 1, return
*false;* - otherwise, for all integers
**m**from 2 to n - 1, check if**n**is divisible by**m**. If it is,**n**is composite; - if no divisors were found, we can conclude, that
**n**is prime.

*Note.* The 1 is not a prime number, because it doesn't satisfy the definition.

## Improving the method

Can we make this simple approach better? Yes. First, let us notice, that we can check divisors less or equal to square root of **n** only. The proof follows.

*Statement.* If **n** has a divisor **d (1 < d < n), **than it has a divisor **d _{0} (1 < d_{0} < √n).**

If **n** is divided by square root entirely, than it is a perfect square and not prime. Otherwise, assume, that first found divisor is **d _{1}, √n < d_{1} < n. **But

**n**is divided entirely by

**d**which is less than

_{2}= n / d_{1},**√n**. Therefore, the assumption is false and if there are a divisor greater than

**√n**, than there is a "pair" less than

**√n.**Statement is proven.

## One more improvement

We should mention one more improvement. Assume, than **n** is odd (2 is not a divisor). If **n** is not divisible by 2 without remainder, than it is not divisible entirely by any other even number. The algorithm after those two improvements changes:

- if number is 1, return
*false;* - if number is 2, return
*true;* - if number is even, return
*false;* - otherwise, for all odd integers
**m**from 3 to**√n**, check if**n**is divisible by**m**. If it is,**n**is composite; - if no divisors were found, we can conclude, that
**n**is prime.

Generalization of this idea is when algorithm checks prime divisors only.

## Complexity analysis

Assuming, that divisibility of two numbers is a unit operation (which is not correct for large numbers), algorithm's complexity is O(√n). The last improvement changes the constant only. When checking just prime divisors, algorithm's complexity becomes O(√n / ln(n)).

The main application of primes is cryptography, which expects us to generate primes with hundreds of digits. Apparently, the algorithm won't check numbers around 10^{100} in a reasonable time. Though, algorithm is applied on practice to do a "pre-check". A huge number being tested for primality is examined to be divisible by first million primes. If no divisors found, probabilistic algorithm is used then.

## First hundred primes

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

## Code snippets

### Java implementation

**public** **boolean** isPrime(**int** number) {

**if** (number == 1)

**return** **false**;

**if** (number == 2)

**return** **true**;

**if** (number % 2 == 0)

**return** **false**;

**for** (**int** d = 3; d <= (**int**) Math.sqrt(number); d++)

**if** (number % d == 0)

**return** **false**;

**return** **true**;

}

### C++ implementation

bool isPrime(int number) {

if (number == 1)

return false;

if (number == 2)

return true;

if (number % 2 == 0)

return false;

for (int d = 3; d <= (int)sqrt((double)number); d++)

if (number % d == 0)

return false;

return true;

}

## Recommended books

- Victor Shoup.
**A Computational Introduction to Number Theory and Algebra.** - Peter J. Giblin.
**Primes and Programming.** - David M. Bressoud.
**Factorization and Primality Testing.** - Hans Riesel.
**Prime Numbers and Computer Methods for Factorization.**

## One response to "Primality test (naive approach) tutorial"

- on April 17, 2009 said:
The for loop in the above code is as:

for (int d = 3; d <= (int)sqrt((double)number); d++)

However since we have already tested for even numbers, i.e. number % 2, we can safely increment the count to d + 2:

for (int d = 3; d <= (int)sqrt((double)number); d = d + 2)

Undoubtedly. But our primary goal was to show the naive approach and it's unsuitability to work in real cryptography applications. We can increase the speed of the algorithm with the enhancement you've suggested, but it still won't give us suitable asymptotic complexity.

## Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.

Every dollar helps!