Wear a helmet. Even when coding.

exercises > prime-testing

Exercise #21: Testing if Number is Prime
by Zoran Horvat @zoranh75
January 06, 2014

Problem Statement

Given an integer number N, N > 1, write a function which returns true if that number is prime and false otherwise. Number is prime if it has no other divisors than 1 and itself.

Example: For numbers 2, 5, 17 function should return true. For number 143 function should return false because that number is divisible by 11 and 13.

Problem Analysis

We can discover that a given number is prime by failing to prove the opposite, i.e. by verifying that there is no eligible value which divides it without remainder. The trick in this task is to properly identify eligible divisors. These should be numbers greater than one which are not equal to the number tested. Further on, there is no point in taking into account values greater than N because none of them could possibly divide N. So, by now we have constrained candidates to set {2, 3, ..., N-1}.

Now suppose that there is such a value k which is the smallest number which divides N:


This implies that m is also a divisor of N. But the fact that k is the smallest divisor implies that m cannot be less than k. From these facts we can derive one important conclusion:

k = {2, 3, ..., sqrt(N)}

This has significantly reduced the problem. But we can make a step further. There is no point in trying to divide N with even values of k, except the trivial candidate 2. This because if N is not divisible by 2, then there is no chance that any other even number could divide it. The same logic goes with number 3. If 3 doesn't divide N, then none other multiple of 3 can divide N either. This leads to an interesting conclusion about possible divisors of N: the only viable candidates that could divide N are values 2, 3 and odd numbers around multiples of 6:

k = {2, 3, ..., 6j+-1}

This opts out roughly two out of three candidates not exceeding square root of N. And here is the pseudocode which solves the problem:

function IsPrime(n)
    result = false
    if n <= 3 then
        result = true
    else if n mod 2 <> 0 AND n mod 3 <> 0 then
            k = 5
            step = 2
            while k * k <= n AND n mod k <> 0
                    k = k + step
                    step = 6 - step

            if n = k OR n mod k <> 0 then
                result = true
    return result


The following C# code is a console application which implements the IsPrime function to test whether its argument is prime or not:

using System;

namespace PrimeNumber

    public class Program

        static bool IsPrime(int n)

            bool result = false;

            if (n <= 3)
                result = true;
            else if (n % 2 != 0 && n % 3 != 0)

                int k = 5;
                int step = 2;

                while (k * k <= n && n % k != 0)
                    k = k + step;
                    step = 6 - step;

                if (n == k || n % k != 0)
                    result = true;


            return result;


        static void Main(string[] args)

            while (true)

                Console.Write("Enter number (zero to exit): ");

                int n = int.Parse(Console.ReadLine());
                if (n <= 0)

                if (IsPrime(n))
                    Console.WriteLine("Number {0} is prime.", n);
                    Console.WriteLine("Number {0} is not prime.", n);





When application above is run, it produces the following output:

Enter number (zero to exit): 2
Number 2 is prime.
Enter number (zero to exit): 3
Number 3 is prime.
Enter number (zero to exit): 17
Number 17 is prime.
Enter number (zero to exit): 18
Number 18 is not prime.
Enter number (zero to exit): 143
Number 143 is not prime.
Enter number (zero to exit): 64657551
Number 64657551 is not prime.
Enter number (zero to exit): 64657553
Number 64657553 is prime.
Enter number (zero to exit): 0

See also:

Published: Jan 6, 2014; Modified: Dec 14, 2014


Zoran is software architect dedicated to clean design and CTO in a growing software company. Since 2014 Zoran is an author at Pluralsight where he is preparing a series of courses on object-oriented and functional design, design patterns, writing unit and integration tests and applying methods to improve code design and long-term maintainability.

Follow him on Twitter @zoranh75 to receive updates and links to new articles.

Watch Zoran's video courses at (requires registration):

Making Your C# Code More Object-Oriented

This course will help leverage your conceptual understanding to produce proper object-oriented code, where objects will completely replace procedural code for the sake of flexibility and maintainability. More...

Advanced Defensive Programming Techniques

This course will lead you step by step through the process of developing defensive design practices, which can substitute common defensive coding, for the better of software design and implementation. More...

Tactical Design Patterns in .NET: Creating Objects

This course sheds light on issues that arise when implementing creational design patterns and then provides practical solutions that will make our code easier to write and more stable when running. More...

Tactical Design Patterns in .NET: Managing Responsibilities

Applying a design pattern to a real-world problem is not as straight-forward as literature implicitly tells us. It is a more engaged process. This course gives an insight to tactical decisions we need to make when applying design patterns that have to do with separating and implementing class responsibilities. More...

Tactical Design Patterns in .NET: Control Flow

Improve your skills in writing simpler and safer code by applying coding practices and design patterns that are affecting control flow. More...

Writing Highly Maintainable Unit Tests

This course will teach you how to develop maintainable and sustainable tests as your production code grows and develops. More...

Improving Testability Through Design

This course tackles the issues of designing a complex application so that it can be covered with high quality tests. More...

Share this article