Efficient prime test

Arnaldo P. Castaño

Rate me:

4.60/5 (6 votes)

12 Nov 2013CPOL1 min read

16.3K

The IsPrime algorithm will always find a number that divides n if it is composed.

Download source code - 0.4 KB

Introduction

Prime numbers are essential in many fields of mathematics and computer science, especially cryptography. An interesting problem arises when we need to decide whether an integer is a prime number.

The straightforward, naïve algorithm for deciding if a number n is prime follows a procedure in which a loop from 2 to n-1 checks every time whether the number representing the step of the loop divides n and in that case returns false.

The previous algorithm runs in O (n). An improvement to the running time of the Naïve prime test can be achieved if we ask ourselves the question: Is it really necessary to loop from 2 to n-1? The answer to this question is no, is not necessary, it would be enough to loop only from 2 to squart(n).

Correctness of the IsPrime algorithm: Let’s assume that all numbers that divide n are greater than squart(n). If this is the case then the smallest number that can divide n is squart(n)+1, but, if n is composed then the smallest numbers dividing n must be greater or equal than [squart(n)+1] [squart(n)+1], but this product is greater than n, which is a contradiction, though there must be at least a number dividing n less than or equal to squart(n) proving that the IsPrime algorithm will always find a number that divides n if it is composed.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By

Arnaldo P. Castaño

Software Developer

Serbia

Computer Scientist and book author living in Belgrade and working for a German IT company. Author of Practical Artificial Intelligence: Machine Learning, Bots, and Agent Solutions Using C# (Apress, 2018) and PrestaShop Recipes (Apress, 2017). Lover of Jazz and cinema Smile | :)

public static bool IsPrime(uint nNumber) { //exceptional case that the function doesn't validate if (nNumber == 2) return true; //even numbers are never prime (except 2), and neither 1 (by convention) if (nNumber % 2 == 0 || nNumber == 1) return false; //the last prime factor possibility for some number N would be Prime(m) where Prime(m + 1) squared exceeds N uint nSqrt = (uint)Sqrt(nNumber); //skip even numbers because if its not divisible by 2 its not divisible by any even number for (uint i = 3; i <= nSqrt; i += 2) if ((nNumber % i) == 0)//if divisible, not prime return false; return true; }

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Efficient prime test

Introduction

License

Comments and Discussions