Share This Article:

A Sieve for Prime Based on Extension Form of Not Prime

Abstract Full-Text HTML Download Download as PDF (Size:50KB) PP. 86-89
DOI: 10.4236/ajcm.2013.31014    3,396 Downloads   5,359 Views  

ABSTRACT

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

(1)

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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

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.

References

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