Sieve of Eratosthenes
Optimizing a rudimentary sieve.
$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.
|