Post Reply 
Sieve of Eratosthenes
12-19-2018, 02:30 PM
Post: #1
Sieve of Eratosthenes
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
Visit this user's website Find all posts by this user
Quote this message in a reply
12-19-2018, 03:24 PM
Post: #2
RE: Sieve of Eratosthenes
I remember doing something similar to solve one of the early puzzles on the Project Euler website Smile
Find all posts by this user
Quote this message in a reply
12-19-2018, 07:00 PM (This post was last modified: 12-24-2018 01:41 PM by Albert Chan.)
Post: #3
RE: Sieve of Eratosthenes
(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 acppmax;
    
:= range(1n+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*pc<=nc+=pa(c):=0// mark composite
    
end;
    return 
a;

Find all posts by this user
Quote this message in a reply
12-20-2018, 06:19 AM (This post was last modified: 12-20-2018 06:23 AM by Thomas Klemm.)
Post: #4
RE: Sieve of Eratosthenes
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
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)