%0 Journal Article
%T A Sieve for Prime Based on Extension Form of Not Prime
%A Gabriele Martino
%J American Journal of Computational Mathematics
%P 86-89
%@ 2161-1211
%D 2013
%I Scientific Research Publishing
%R 10.4236/ajcm.2013.31014
%X <p align=\"justify\">
	<span style=\"font-family:Verdana;\"> </span> 
</p>
<p align=\"justify\">
	<span><span style=\"font-family:Verdana;\">This paper will illustrate two versions of an algorithm for finding prime number up to </span><i><span style=\"font-family:Verdana;\">N</span></i><span style=\"font-family:Verdana;\">, which give the first version complexity </span></span> 
</p>
<span><span></span></span> 
<p style=\"text-align:right;\" align=\"justify\">
	<span style=\"font-family:Verdana;\"><span style=\"font-family:Verdana;\"><img alt=\"\" src=\"Edit_e3811f7f-8951-4765-ab1b-63b6bfdfe67a.bmp\" width=\"221\" height=\"39\" /><span style=\"font-family:Verdana;\"> </span></span></span><span style=\"font-family:Verdana;\">(1)</span> 
</p>
<p align=\"justify\">
	<span><span style=\"font-family:Verdana;\">where </span><i><span style=\"font-family:Verdana;\">c</span></i><span style=\"font-family:Verdana;\">1,</span></span><span> </span><i><span style=\"font-family:Verdana;\">c</span></i><span><span style=\"font-family:Verdana;\">2 are constants, and </span><i><span style=\"font-family:Verdana;\">N</span></i><span style=\"font-family:Verdana;\"> is the input dimension, and gives a better result for the second version. The method is based on an equation that expresses the behavior of not prime numbers. With this equation </span></span><span style=\"font-family:Verdana;\">it </span><span style=\"font-family:Verdana;\">is possible to construct a fast iteration to verify if the not prime number is generated by a prime and with which parameters. The second method differ</span><span style=\"font-family:Verdana;\">s</span><span style=\"font-family:Verdana;\"> because </span><span style=\"font-family:Verdana;\">it </span><span style=\"font-family:Verdana;\">do</span><span style=\"font-family:Verdana;\">es</span><span style=\"font-family:Verdana;\"> not pass other times over a number that has been previously evaluated as not prime. This is possible for a recurrence of not prime number that </span><span style=\"font-family:Verdana;\">is</span><span><span style=\"font-family:Verdana;\"> (mod 3) = 0. The complexity in this case is better than the first. The comparison is made most with Mathematics than by computer calculation as the number </span><i><span style=\"font-family:Verdana;\">N</span></i><span style=\"font-family:Verdana;\"> should be very big to appreciate the difference between the two versions. Anyway the second version result</span></span><span style=\"font-family:Verdana;\">s</span><span style=\"font-family:Verdana;\"> better. The algorithms have been
%K Prime Number
%K Equation
%K Sieve
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=29529