A Sieve for Prime Based on Extension Form of Not Prime

DOI: 10.4236/ajcm.2013.31014   PDF   HTML     3,593 Downloads   5,546 Views  


This paper will illustrate two versions of an algorithm for finding prime number up to N, which give the first version complexity


where c1, c2 are constants, and N 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 it 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 differs because it does 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 is (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 N should be very big to appreciate the difference between the two versions. Anyway the second version results better. The algorithms have been developed in an object oriented language.

Share and Cite:

G. Martino, "A Sieve for Prime Based on Extension Form of Not Prime," American Journal of Computational Mathematics, Vol. 3 No. 1, 2013, pp. 86-89. doi: 10.4236/ajcm.2013.31014.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Wikipedia. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
[2] A. O. L. Atkin and D. J. Bernstein, “Prime Sieves Using Binary Quadratic Forms,” Mathematics of Computation, Vol. 73, 2004, pp. 1023-1030. doi:10.1090/S0025-5718-03-01501-1
[3] Wikipedia. http://en.wikipedia.org/wiki/Sieve_of_Atkin
[4] http://math.stackexchange.com/questions/141224/finite-sum-of-reciprocal-odd-integers
[5] T. M. Apostol, “Calculus I,” Bollati Boringhieri, 2003, p. 481.
[6] Wikipedia. http://en.wikipedia.org/wiki/Harmonic_series

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.