﻿A Sieve for Prime Based on Extension Form of Not Prime

American Journal of Computational Mathematics
Vol.3 No.1(2013), Article ID:29529,4 pages DOI:10.4236/ajcm.2013.31014

A Sieve for Prime Based on Extension Form of Not Prime

Gabriele Martino

Via Cornelia, Rome, Italy

Email: martino.gabri@gmail.com

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.

Received October 10, 2012; revised November 21, 2012; accepted December 3, 2012

Keywords: Prime Number; Equation; Sieve

1. Introduction

Prime numbers are numbers that can be divided only by one or by themselves in order to get integer number. They are probably the most famous number’s series. For finding the primes up to N, 2 main Sieves have been developed. One is the Eratosthenes Sieve  that is based on eliminating the not prime that is generated by multiplies of numbers over a list. For this Sieve the complexity is . Another Sieve is the Atkins and Bernstein Sieve [2,3], which is based on the remainder of modulo sixty.

In this case the complexity is . This paper aims to continue on this work improving the sieving. Observe that all the odd numbers are not prime if they are of the form (2)

where p is a prime number > 1 and and np is for not prime.Taking all the numbers for x odd where the set of the odds is bigger than the set of prime, and k integer is possible to cover all the Not Prime set. There are some repetition in particular those that have remainder 0 divided by 3 (Of course the x = 3 series must be generated first and after a number np can be considered not prime already counted if divided by 3 gives remainder 0). In the first algorithm we give a solution with repetition in building the set of not prime. In the second we avoid the repetition considering that a square number generated from an odd, generate vary k, two possible kind of repetition: in the first is repeated for each k (mod 3) = 2, and in the second for each k (mod 3) = 3.

2. Methods

2.1. Method I

The follow is a explanation of the method for the search of prime. We want to count the prime up to N. We extend our iteration variable in the interval . The numbers (mod 2) = 0 are not primes. For the prime number we generate first as not prime and after generate . With p that can be an also an odd number because the set of primes is in the set of odds except that number 2 and . The algorithm is presented in the appendix.

2.2. Method II

Another better result can achieved thinking that the numbers (mod 3) = 0, repeat in the count. I observed that there are 3 kind of repetition. for every k like . for every k counted 1 (not counted 0) in the sequence 101-101-101 like 5. And for every k in the sequence 110-110-110 like 7.

We should make it in a way that affords us to go over a case of 0 and go to next k = k + 1, avoiding count repetition.

Example 7 × 7 = 49 (mod 3 different from 0) not counted; 7 × 7 + 2 × 7 = 63 (mod 3 = 1) already counted in the 3 sequence; 7 × 7 + 4 × 7 = 77 not counted. They gives the sequence 101.

3. Results

To count the primes up to 1,000,000 both methods take 3 seconds. This means that only for bigger N a comparison of methods is possible. The second should anyway take less time than the first. The test has been done with an machine Asus Intel i7 with 4 GB Ram, with an Operative System Windows 7 and the platform Java.

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

Appendix

Algorithm I

N we count the prime up to N primes [N] = true for each element for do primes [i] = false wang#title3_4:spend for

for do while do if || then end if end while wang#title3_4:spend for

return primes

Computational Complexity of Algorithm I

We call C(A) the complexity of the second loop, whereas, T(A) is the complexity of all the code. We use the approximation (3)

as stated in (4)

and (5)

as stated in [5,6]

The complexity of the first method is given by the 2 nested loop in the algorithm.  Evaluating the second member with (3) Taking out of the first member the constant operation Changing the form for odd number at first member Extending the sum adding and subtracting the same element Using the (4) Using the (5) That asymptotically goes like Algorithm II

N we want to count the primes until N primes [N] = true for do primes [i] = false

end if

for do j = square k = 0 condition = "";

if mod 3 == 0 And then condition = "101";

else if mod 3 == 0 And then condition = "110"

else if then condition = "111" end if

while And! ("111") do if j mod 3! = 0 or i == 2 then wang#title3_4:spwang#title3_4:spend if if condition = ("101") And then wang#title3_4:spwang#title3_4:spend if

if condition = ("110") And then wang#title3_4:spwang#title3_4:spend if end while

end for

returns primes