Click here to Skip to main content
Click here to Skip to main content

Efficient prime test

, 12 Nov 2013
Rate this:
Please Sign up or sign in to vote.
The IsPrime algorithm will always find a number that divides n if it is composed.

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)

About the Author

arnaldo.skywalker
Software Developer
Cuba Cuba
I'm a programmer and mathematician, graduated of Computer Science. Lover of Jazz, music, cinema and art in general.

Comments and Discussions

 
QuestionThis is not "efficient" prime test Pinmemberfulloflove28-Feb-14 17:15 
This is very "trivial" and should not be considered efficient.
 
No need to test for all numbers from 2 to sqrt(n). Just odd numbers is enough, in that case you reduce the number of branch by 2. You can even only check for numbers in the form 6n+1 or 6n+5 since the remainder when dividing a prime by 6 must be 1 or 5, you can easily check this by math. Also, square root is a heavy computational operation, replace it by i*i <= n may be better.
 
int isPrime(unsigned int n)
{
    if (n == 2 || n == 3 || n = 5)
        return 1;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0)
        return 0;
 
    unsigned int i = 7, step = 7 - 5;
    while (i*i <= n)
    {
        if (n % i == 0)
            return 0;
        step = 6 - step;
        i += step;
    }
    return 1;
}
 
For even more efficient you can check for multiple of larger numbers with remainders in form (ak + b) where a > 6
QuestionNot the prime example of optimization PinmemberCaldasGSM12-Nov-13 7:37 
AnswerRe: Not the prime example of optimization Pinmemberarnaldo.skywalker12-Nov-13 8:36 
GeneralMessage Removed Pinmemberbharat_h0312-Nov-13 22:49 
GeneralRe: Not the prime example of optimization Pinmemberarnaldo.skywalker14-Nov-13 4:07 
GeneralRe: Not the prime example of optimization Pinmemberbharat_h0321-Nov-13 0:01 
QuestionThere are several prime sieves. PinprotectorPete O'Hanlon12-Nov-13 5:59 
AnswerRe: There are several prime sieves. Pinmemberarnaldo.skywalker12-Nov-13 6:53 
GeneralRe: There are several prime sieves. PinprofessionalPIEBALDconsult12-Nov-13 11:06 
GeneralRe: There are several prime sieves. Pinmemberarnaldo.skywalker14-Nov-13 4:11 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Mobile
Web03 | 2.8.140718.1 | Last Updated 12 Nov 2013
Article Copyright 2013 by arnaldo.skywalker
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid