HP Forums

The program SIEVEMIN shows a miniature version of the famous Sieve of Eratosthenes. The Sieve of Eratosthenes is a Greek algorithm that determines prime numbers from 2 to N through eliminating multiplies.

Code:

sub1(); // subroutine

EXPORT SIEVEMIN()

BEGIN

// 2018-12-18 EWS

// Mini Sieve

HFormat:=0; // standard

PRINT();

PRINT("Mini Sieve");

WAIT(1);

LOCAL M0,T,R,C,K;

T:=1;

M0:=MAKEMAT(0,7,7);

FOR R FROM 1 TO 7 DO

FOR C FROM 1 TO 7 DO

M0(R,C):=T;

T:=1+T;

END;

END;

sub1(M0);

M0(1,1):=0;

FOR K FROM 2 TO 7 DO

FOR R FROM 1 TO 7 DO

FOR C FROM 1 TO 7 DO

IF FP(M0(R,C)/K)==0 AND 

M0(R,C)>K THEN

M0(R,C):=0;

sub1(M0);

END;

END;

END;

END;

// end of program

END;

sub1(M1)

BEGIN

PRINT();

LOCAL I;

FOR I FROM 1 TO 7 DO

PRINT(row(M1,I));

END;

WAIT(0.5);

END;

Blog link: https://edspi31415.blogspot.com/2018/12/...ve-of.html

I remember doing something similar to solve one of the early puzzles on the Project Euler website Smile

(12-19-2018 02:30 PM)Eddie W. Shore Wrote: [ -> ]FOR K FROM 2 TO 7 DO
FOR R FROM 1 TO 7 DO
FOR C FROM 1 TO 7 DO
IF FP(M0(R,C)/K)==0 AND M0(R,C)>K THEN M0(R,C):=0; ...

I don't think the code is really a prime sieve.
A true sieve does not need any divisibility test.
Also, looping count is very high = 6x7x7 = 294

I think sieve should be like below code.
To get your 7x7 matrix, do list2mat(sieve(7*7), 7)

PHP Code:

sieve(n) := {
    local a, c, p, pmax;
    a := range(1, n+1); a(1) := 0;       // 1 is not prime
    pmax := floor(sqrt(n));
    for p from 2 to pmax do
        if (a(p) == 0) continue;         // skip composite
        for(c:=p*p; c<=n; c+=p) a(c):=0; // mark composite
    end;
    return a;
} 

There is a program written by C.Ret for the HP-29C and also for the HP-41C that uses a min-heap as data-structure instead of an array due to memory limitations.

Cheers
Thomas

Eddie W. Shore

grsbanks

Albert Chan

Thomas Klemm