12,831,676 members (32,903 online)
Tip/Trick
Add your own
alternative version

#### Stats

7.8K views
45 downloads
5 bookmarked
Posted 12 Nov 2013

# 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)

## About the Author

 Software Developer 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...

 Pro Pro

## Comments and Discussions

 First Prev Next
 This is not "efficient" prime test fulloflove28-Feb-14 18:15 fulloflove 28-Feb-14 18:15
 Not the prime example of optimization CaldasGSM12-Nov-13 8:37 CaldasGSM 12-Nov-13 8:37
 Re: Not the prime example of optimization arnaldo.skywalker12-Nov-13 9:36 arnaldo.skywalker 12-Nov-13 9:36
 Message Removed bharat_h0312-Nov-13 23:49 bharat_h03 12-Nov-13 23:49
 Re: Not the prime example of optimization arnaldo.skywalker14-Nov-13 5:07 arnaldo.skywalker 14-Nov-13 5:07
 I really don't understand why you have sqrt(n) * n == n as a condition, I believe it's only satisfied when n=1. Also, sqrt(n)/2 is not a good upper bound if n=25 then sqrt(25)=5 and 5/2 = 2.5 so you will return that 25 is prime.
 Re: Not the prime example of optimization bharat_h0321-Nov-13 1:01 bharat_h03 21-Nov-13 1:01
 There are several prime sieves. Pete O'Hanlon12-Nov-13 6:59 Pete O'Hanlon 12-Nov-13 6:59
 Re: There are several prime sieves. arnaldo.skywalker12-Nov-13 7:53 arnaldo.skywalker 12-Nov-13 7:53
 Re: There are several prime sieves. PIEBALDconsult12-Nov-13 12:06 PIEBALDconsult 12-Nov-13 12:06
 Re: There are several prime sieves. arnaldo.skywalker14-Nov-13 5:11 arnaldo.skywalker 14-Nov-13 5:11
 Last Visit: 31-Dec-99 19:00     Last Update: 30-Mar-17 17:02 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170326.1 | Last Updated 12 Nov 2013
Article Copyright 2013 by arnaldo.skywalker
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid