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
