## Monday, 17 September 2012

### LUA PRIME CALCULATOR using preprocessing based on Sieve of Eratosthenes

This article shows a lua script to calculate an ordered prime list starting with 2, 3, 5, 7, etc.

We are going to improve former lua prime calculator using a preprocessing table.
This table will allow us to discard quickly some numbers and its multiples.

Within this lua script, first we perform some preprocessing, and after that actual prime testing for remaining numbers are performed.

#### Sieve of Eratosthenes

Sieve of Eratosthenes is an algorithm to calculate a prime number list up to a chosen number.

In this program we will use this algorithm to generate a preprocessing table.

Some examples are useful to show how preprocessing table works:

Tables are generated using a sequence with first prime numbers.

E.g:

Preprocessing table for 2

{2}

So we will test numbers this way:
We start with number one, and sum to it the first number from preprocessing table:
1+2 = 3 (3 is the next number to test for primality)

Once preprocessing table has completed, we start from first element again (2):
3+2 = 5

5+2 = 7

7+2 = 9
etc

Preprocessing table for 2 and 3:
{4,2}

First number to test:
1+4 = 5
5+2 = 7

We start again from the beginning of the table:
7+4 = 11
11+2 = 13

13+4 = 17
17+2 = 19
etc

Preprocessing table for 2, 3 and 5:
[6,4,2,4,2,4,6,2]

1+6 = 7
7+4 = 11
11+2 = 13
13+4 = 17
17+2 = 19
19+4 = 23
23+6 = 29
29+2 = 31

After reaching last element in the table we start again:
31+6 = 37
37+4 = 41
41+2 = 43
43+4 = 47
47+2 = 49
etc

Increasing the preprocessing table has an exponential cost in memory size and cpu cycles, and improvements for big preprocessing tables are small.

No preprocess at all: (No numbers are discarded) 1/1 -> 100% cost
2 {2} 1/2 -> 50% We test only 50% of numbers.
2,3 {2,4} 2/6 -> 33% We test 33% of numbers.
2,3,5 {6,4,2,4,2,4,6,2} 8/30 -> 26.6% We test 26.6% of numbers.
...

#### PREPROCESSING FUNCTION

Let's look at the preprocess function code:

```local preproc = {2}
local primes = {2}

local function preprocess()

-- We know always prime number calculated using the preprocessing table is a prime
-- get next prime
local k = 1
local next = preproc[1] + k
print("next: "..next)
table.insert(primes, next)

-- Each level table size is multiplied by last prime number added.
local new_preproc = {}
for i=1,next do
for j=1,#preproc do
table.insert(new_preproc, preproc[j])
end -- for
end -- for
preproc = new_preproc

-- This loop removes from the table multiples of last added prime number
local next_n = 1
local l = 1
local second = 1
local next_big = next * second
new_preproc={}
carry = 0
for i=1,#preproc do
next_n = next_n + preproc[i]
if(next_n < next_big) then
table.insert(new_preproc, preproc[i]+carry)
carry = 0
else
while(next_n > next_big) do
second = second + preproc[l]
l = l + 1
next_big = next * second
end -- while
if(next_n < next_big) then
table.insert(new_preproc, preproc[i]+carry)
carry = 0
elseif(next_n == next_big) then
second = second + preproc[l]
l = l + 1
next_big = next * second
carry = carry + preproc[i]
end -- if
end -- if
end -- for
preproc = new_preproc

end -- function
```

Every time preprocess function is called, a prime is added to primes list, and preproc table is increased as necessary.

Its increase in memory size and cpu cycles required is exponential.

#### EXECUTING THE SCRIPT

Copy following code in a file: prime_calculator.lua

`\$ chmod a prime_calculator.lua` # Give execution permissions to it.
`\$ ./prime_calculator.lua 10000 5`

or

`\$ ./prime_calculator 10000 5 +` # If there is a third argument then prime list result it is shown in the end.

`\$ ./prime_calculator 10000 5` means: perform 5 preprocessing levels and then calculate first 10000 prime numbers.

#### LUA CODE

```#! /usr/bin/lua

local top = tonumber(arg[1])
local top_prep = tonumber(arg[2])

local preproc = {2}
local primes = {2}

local function preprocess()
-- get next prime
local k = 1
local next = preproc[1] + k
print("next: "..next)
table.insert(primes, next)
local new_preproc = {}
for i=1,next do
for j=1,#preproc do
table.insert(new_preproc, preproc[j])
end -- for
end -- for
preproc = new_preproc
local next_n = 1
local l = 1
local second = 1
local next_big = next * second
new_preproc={}
carry = 0
for i=1,#preproc do
next_n = next_n + preproc[i]
if(next_n < next_big) then
table.insert(new_preproc, preproc[i]+carry)
carry = 0
else
while(next_n > next_big) do
second = second + preproc[l]
l = l + 1
next_big = next * second
end -- while
if(next_n < next_big) then
table.insert(new_preproc, preproc[i]+carry)
carry = 0
elseif(next_n == next_big) then
second = second + preproc[l]
l = l + 1
next_big = next * second
carry = carry + preproc[i]
end -- if
end -- if
end -- for

preproc = new_preproc

end -- function

for j=1,top_prep do
preprocess()
end

local total_prep = #preproc

local total = #primes
local sqrt = math.sqrt
local pos = 1
local i = 1 + preproc[pos]

while(total<top) do
local is_prime = true
local max = sqrt(i)
for j=1, total do
local div = primes[j]
if(div>max) then
break
end
if(i%div==0) then
is_prime = false
break
end
end
if(is_prime) then
table.insert(primes, i)
total = total + 1
end
pos = pos + 1
if(pos>total_prep) then pos=1 end
i = i + preproc[pos]
end -- while

if(arg[3]~=nil) then
for i=1,# primes do
print(primes[i])
end
end```

#### REFERENCE

Sieve of Eratosthenes (Wikipedia)

#### YOU MAY ALSO BE INTERESTED IN:

Lua: Calculate a prime number list

Calculate a PRIME number LIST using C language