TITLE:
A Sieve for Prime Based on Extension Form of Not Prime
AUTHORS:
Gabriele Martino
KEYWORDS:
Prime Number; Equation; Sieve
JOURNAL NAME:
American Journal of Computational Mathematics,
Vol.3 No.1,
March
29,
2013
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.