This R code implements the idea that if we remove all numbers which are multiples of lower numbers, then we will be left with primes. It is not necessary to check all divisors, checking prime divisors is enough. And its not necessary to check all primes less than our upper limit. If we want to sieve all integers upto 1024, for example, we note that 1024= 32 times 32. So if there is a factor greater than 32, there will be another one which is less than 32, and we would already have found that. so no need to go for primes beyond 32, to sieve upto 1024.
The code consists of the two parts The fisrt is a function which we call sieve. It takes a vector “up’ of integers upto some upper limit as one argument. It also needs a list of primes upto the square root of up, which we call ‘lp’. And it gives out a longer list of primes, going upto ‘up’.
#yet another implementation of sieve
sieve <- function(lp,up) {
for (d in lp) {
up <- up[!(up%%d==0)]
}
return(c(lp,up))
}note that the sieving deletes the members of lp as well (because they are divisible by lp) and therefore we attache them pack to the sieved list after all nonprime numbers have beenremoved from lp. Now the next step is to start with c(2), a vector of length one containing the lowest prime. We can use this to sieve upto 4, which will give us 2 and 3, now we can sieve upto 9, (actually the highest member is 7) so now we can sieve upto 49, and keep going. That is achieved in a for loop which calls the function sieve repeatedly.
t<-c(2);b<-FALSE
while(1==1)
{ tmax<-t[length(t)]
n<- tmax^2
if (n>1000){n<-1000;b=TRUE}
p<- 2:n
t<-sieve(t,p);if(b) break
}Note that break out after reachig the maximum number we are interested in, viz, 1000, using the logical variable b.