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 [1] 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.
Appendix
Algorithm I
N we count the prime up to N primes [N] = true for each element
![](https://www.scirp.org/html/14-1100181\0b390703-0011-4fff-8818-850dae27b440.jpg)
for
do primes [i] = false
![](https://www.scirp.org/html/14-1100181\7e076ca2-d307-483d-b81f-aa25213477f0.jpg)
wang#title3_4:spend for
for
do
![](https://www.scirp.org/html/14-1100181\2a75e8a9-4304-43d6-93c4-c3d8eae9687d.jpg)
while
do if
||
then
![](https://www.scirp.org/html/14-1100181\8b11df47-d4e7-416c-8e00-f45ca4572179.jpg)
end if
![](https://www.scirp.org/html/14-1100181\1e5f7701-cfe2-44d1-9814-267b8f4d90c0.jpg)
end while
![](https://www.scirp.org/html/14-1100181\cac263b9-c01d-4135-9493-33d040d995d3.jpg)
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.
![](https://www.scirp.org/html/14-1100181\18e6b15e-264f-43cb-8fde-c873476e0baa.jpg)
We use the approximation
(3)
as stated in [4]
(4)
and
(5)
as stated in [5,6]
The complexity of the first method is given by the 2 nested loop in the algorithm.
![](https://www.scirp.org/html/14-1100181\52e0850a-f678-4929-8724-5a925c30e90f.jpg)
Separating the members of addition
![](https://www.scirp.org/html/14-1100181\2af4a891-86d1-439d-acf3-6a9bb5706d61.jpg)
Evaluating the second member with (3)
![](https://www.scirp.org/html/14-1100181\6f2489cc-32ef-48df-88fe-f1471da8660d.jpg)
Taking out of the first member the constant operation
![](https://www.scirp.org/html/14-1100181\26564320-cd42-4b50-8e08-c591fd9768d8.jpg)
Changing the form for odd number at first member
![](https://www.scirp.org/html/14-1100181\ea6a0e3a-dd73-4b7d-ad55-c62011b92dab.jpg)
Extending the sum adding and subtracting the same element
![](https://www.scirp.org/html/14-1100181\56fbcb57-8af6-4406-bc3e-6a78670bf701.jpg)
Using the (4)
![](https://www.scirp.org/html/14-1100181\2112f292-be2c-4ec2-94e2-1342ec9e395e.jpg)
Using the (5)
![](https://www.scirp.org/html/14-1100181\f15cc62e-14a1-4522-8d71-dd7cb0db318c.jpg)
That asymptotically goes like
![](https://www.scirp.org/html/14-1100181\d02a3dff-fb57-4bc9-ad14-3f78bbef8aab.jpg)
Algorithm II
N we want to count the primes until N primes [N] = true
![](https://www.scirp.org/html/14-1100181\e63c007d-1ed7-4576-8903-d1c6bcc5f4c5.jpg)
for
do primes [i] = false
end if
for
do
![](https://www.scirp.org/html/14-1100181\ffb221cf-b67d-4d72-9f06-795909aba288.jpg)
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"
![](https://www.scirp.org/html/14-1100181\a4cec24b-4cd0-46fd-823c-2b32be13eb78.jpg)
end if
while
And! ("111") do if j mod 3! = 0 or i == 2 then
![](https://www.scirp.org/html/14-1100181\2d59e967-c076-435f-a3ec-3ad879b0058e.jpg)
wang#title3_4:spwang#title3_4:spend if
![](https://www.scirp.org/html/14-1100181\1ed00cda-0f1c-465e-b6f5-7a518203a967.jpg)
if condition = ("101") And
then
![](https://www.scirp.org/html/14-1100181\d82f3bfd-5acc-4fd2-9512-287bfd51d177.jpg)
wang#title3_4:spwang#title3_4:spend if
if condition = ("110") And
then
![](https://www.scirp.org/html/14-1100181\c90bdb1a-9762-41fb-a7ea-005739b2fd88.jpg)
wang#title3_4:spwang#title3_4:spend if
![](https://www.scirp.org/html/14-1100181\ed2e421a-264b-4dbb-903c-f3bebd976e4f.jpg)
end while
end for
returns primes