Eratosthenes was the third librarian of the famous library in Alexandria and an outstanding scholar. The Sieve of Eratosthenes is an algorithm for collecting prime numbers, the invention of which he is credited with. Further details may be found at the Wikipedia link for Eratosthenes (http://en.wikipedia.org/wiki/Eratosthenes).
The Algorithm works as follows :
To collect all Prime numbers below a certain number (say N) start by first identifying all composite numbers and removing them from a predefined numerical sequence ( 1 to N ). Thus, whatever remains are all prime numbers.
The identification of Composite numbers is done by iteratively finding the multiples of all numbers from 2 (1 is not a prime number) till the maximum limit and removing the composite numbers at each step.
I.e, All multiples of 2 (excluding 2 itself) are removed. The next available number is found. In this case it is 3.
Then All multiples of 3 (excluding 3 itself) are removed. The next available number is found. In this case it is 5.
Then All multiples of 5 (excluding 5 itself) are removed. The next available number is found. In this case it is 7.
And so on till the maximum limit is reached.
I attempt here to provide an SAP implementation of the Sieve of Eratosthenes.
DATA : var type i, max type i,
temp type i, count type i value 2,
t_prime type table of i, wa_prime type i.
SELECTION-SCREEN begin of block b1 with frame.
PARAMETERS : limit type i.
SELECTION-SCREEN end of block b1.
DO limit times.
var = var + 1.
APPEND var to t_prime.
ENDDO.
DELETE t_prime from 1 to 1.
max = var.
var = 2.
WHILE var <= max.
DO.
temp = var * count.
DELETE t_prime where table_line = temp.
IF sy-subrc = 0.
count = count + 1.
ELSEIF temp <= max.
count = count + 1.
ELSE.
EXIT.
ENDIF.
ENDDO.
READ TABLE t_prime into wa_prime with key table_line = var.
var = sy-tabix + 1.
READ TABLE t_prime into var index var.
IF sy-subrc = 0.
count = 2.
ELSE.
EXIT.
ENDIF.
ENDWHILE.
LOOP AT t_prime into wa_prime.
write : / wa_prime.
ENDLOOP.
An execution of the above program has yielded accurate results finding all prime numbers upto 30,000.
I am sure that this may be optimized further, in terms of logic as well as implementation.
However, I have attempted to remain true to the original Algorithm of the Sieve of Eratosthenes.
