Critticall: Sieve of Eratosthenes


$declareint two index primecandidate upto nonprime one

//The array of zeros
$dimension sieve[1000]
$invar upto (999) sieve[upto]()

// up to where primes should be denoted
$rinvar upto (1,999) sieve[upto]()

//Output variable is sieve[1000] - upto(1,999) elements of sieve[] array.
$retvar sieve[]

//Sound when better program is found is ON.
$sound on

//the beginning of the program segment
two=2;
index=0;
sieve[index]=two;   // special status of 0
index=1;
sieve[index]=two;   // special status of 1


//Beginning of the enhancing segment. Program lines above, will not be enhanced.
$bes
primecandidate=2;    //the first or seed prime
one=1;               //one (1)

while (primecandidate<upto) {
    nonprime=primecandidate+primecandidate;
    while (nonprime<=upto) {
       sieve[nonprime]=one;
       nonprime=nonprime+primecandidate;
    }
    primecandidate++;
}
//End of the enhancing segment.
$ees

We have got this improved algorithm, by using which, it's faster to build a sieve array, than just to count zeros (or ones) in an already built sieve, for up to several thousand large arrays! One may ask, what happens, when this simple count is subjected to Critticall. Well, only the odd places are checked, if they are 0 or 1, after the optimization has been done. That way, the counting becomes faster than the prime setting, again.



 $DECLAREINT two index primecandidate one upto critticall1 critticall2 

 $DIMENSION sieve[1000]
 $INVAR upto(999) sieve[upto]()
 $SOUND ON
 $RINVAR upto(1,999) sieve[upto](0,0)
 $RETVAR sieve[] 

// int sieve[1000]; int two=0;int index=0;int primecandidate=0;int one=0;int upto=0;
// int critticall1=0;int critticall2=0;

two=2;
index=0;
sieve[index]=two;
index=1;
sieve[index]=two;
$BES
two+=1;
critticall2=two*two;
one=critticall2-two;
while (critticall2<=upto) {
    sieve[critticall2]=index;
    critticall2=critticall2+one;
}
two+=1;
while (two<=upto) {
    sieve[two]=index;
    two+=1;
    critticall2=two*two;
    if (critticall2<=upto) {
        primecandidate=sieve[critticall2];
        if (critticall1==primecandidate) {
            one=two+two;
            sieve[critticall2]=index;
            critticall2=critticall2+one;
            while (critticall2<=upto) {
                primecandidate=sieve[critticall2];
                if (critticall1==primecandidate) {
                    sieve[critticall2]=index;
                }
                critticall2=critticall2+one;
            }
        }
    }
    two+=1;
}
$EES

Everything has been (re)invented here. After several hours, Critticall has optimized the basic Sieve with those nifty tricks, by which you can recognize a good sieve program. Setting only the multiples of primes and setting only from the square (of a previously this way determinate prime) up. What we've got, is a very efficient algorithm.