12,070,248 members (27,667 online)
Tip/Trick
alternative version

6.5K views
5 bookmarked
Posted

Efficient prime test

, 12 Nov 2013 CPOL
 Rate this:
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.

Share

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

 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: 9-Feb-16 12:22 Refresh 1