# The Sieve of Eratosthenes

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.

1 Comment
You must be Logged on to comment or reply to a post.
• Ravi,
I really love the way you use that t_prime table. It looks great in the Debugger and I found it very instructive.
But the DELETE takes lots of time “squeazing” the table.
I tried to emulate Erathostenes method even more closely and wrote this little program:

DATA : var type i, elim type i,
t_prime type table of x, wa_prime, no_prime type x.

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 ’01’ to t_prime.
ENDDO.
MODIFY t_prime INDEX 1 FROM no_prime.

var = 2.
WHILE var <= limit.
elim = var.

DO.
elim = elim + var.
IF elim <= limit.
MODIFY t_prime INDEX elim FROM no_prime.
ELSE.
EXIT.
ENDIF.
ENDDO.

DO.
var = var + 1.
READ TABLE t_prime INDEX var INTO wa_prime.
IF wa_prime <> no_prime.
EXIT.
ENDIF.
ENDDO.

ENDWHILE.

LOOP AT t_prime TRANSPORTING NO FIELDS WHERE table_line = ’01’.
WRITE : / sy-tabix.
ENDLOOP.

This runs rather fast even with numbers up to 10,000,000.