primality_test.cpp File Reference

Primality test implementation. More...

#include <iostream>

Include dependency graph for primality_test.cpp:

Functions
bool	IsPrime (int number)
int	main ()

Detailed Description

Primality test implementation.

A simple and efficient implementation of a function to test if a number is prime, based on the fact that

‍Every Prime number, except 2 and 3, are of the form \(6k\pm1\) for integer values of k.

This gives a 3x speed improvement.

Function Documentation

IsPrime()

bool IsPrime

(

int

number

)

Check if a number is prime

Parameters

[in]

number

number to check

Returns

true if prime else false

                         {
    if (((!(number & 1)) && number != 2) || (number < 2) ||
        (number % 3 == 0 && number != 3))
        return false;
 
    for (int k = 1; 36 * k * k - 12 * k < number; ++k) {
        if ((number % (6 * k + 1) == 0) || (number % (6 * k - 1) == 0))
            return false;
    }
    return true;
}

main()

int main

(

void

)

main function

           {
    // Main Function
    std::cout << "Enter the value of n to check if Prime\n";
    int n;
    std::cin >> n;
    if (IsPrime(n))
        std::cout << n << " is Prime" << std::endl;
    else
        std::cout << n << " is not Prime" << std::endl;
 
    return 0;
}

Here is the call graph for this function: