A Sieve for Prime Based on Extension Form of Not Prime

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 c 1, c 2 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 differ s because it do es 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 result s better. The algorithms have been developed in an object oriented language.