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