Click here to Skip to main content
12,242,812 members (44,062 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

6.8K views
43 downloads
5 bookmarked
Posted

Efficient prime test

, 12 Nov 2013 CPOL
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)

Share

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.

You may also be interested in...

Comments and Discussions

 
QuestionThis is not "efficient" prime test Pin
fulloflove28-Feb-14 18:15
memberfulloflove28-Feb-14 18:15 
QuestionNot the prime example of optimization Pin
CaldasGSM12-Nov-13 8:37
memberCaldasGSM12-Nov-13 8:37 
AnswerRe: Not the prime example of optimization Pin
arnaldo.skywalker12-Nov-13 9:36
memberarnaldo.skywalker12-Nov-13 9:36 
GeneralMessage Removed Pin
bharat_h0312-Nov-13 23:49
memberbharat_h0312-Nov-13 23:49 
GeneralRe: Not the prime example of optimization Pin
arnaldo.skywalker14-Nov-13 5:07
memberarnaldo.skywalker14-Nov-13 5:07 
GeneralRe: Not the prime example of optimization Pin
bharat_h0321-Nov-13 1:01
memberbharat_h0321-Nov-13 1:01 
QuestionThere are several prime sieves. Pin
Pete O'Hanlon12-Nov-13 6:59
protectorPete O'Hanlon12-Nov-13 6:59 
Why not use something like the Sieve of Eratosthenes to sort this out.
AnswerRe: There are several prime sieves. Pin
arnaldo.skywalker12-Nov-13 7:53
memberarnaldo.skywalker12-Nov-13 7:53 
GeneralRe: There are several prime sieves. Pin
PIEBALDconsult12-Nov-13 12:06
professionalPIEBALDconsult12-Nov-13 12:06 
GeneralRe: There are several prime sieves. Pin
arnaldo.skywalker14-Nov-13 5:11
memberarnaldo.skywalker14-Nov-13 5:11 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    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 | Terms of Use | Mobile
Web02 | 2.8.160426.1 | Last Updated 12 Nov 2013
Article Copyright 2013 by arnaldo.skywalker
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid