### 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

## 0 comentarios:

Post a Comment