O
Oswald Kluge
Dear Reader,
I'm trying to implement the following short algorithm:
Given a number n, remove all the multiples of n
from the list of non-negative numbers from 1 through a limit k.
My solution is to take an array with all entries '1' and iterate
over it in steps of n, setting the current pointer to '0'.
Here's the code:
const LIMIT=k+1;
unsigned char Sieve[LIMIT];
memset(Sieve,1,LIMIT); // initialise all entries to '1'
for(i=n;i<LIMIT;i+=n) {Sieve=0;}
As k gets large this implementation is really slow for small n,
especially if you have to sieve more than one n. Is there a
more efficient way to implement this? Are there fast memory
operators like memset in c++ for this task?
Thanks for your help!
Best,
Oswald Kluge
I'm trying to implement the following short algorithm:
Given a number n, remove all the multiples of n
from the list of non-negative numbers from 1 through a limit k.
My solution is to take an array with all entries '1' and iterate
over it in steps of n, setting the current pointer to '0'.
Here's the code:
const LIMIT=k+1;
unsigned char Sieve[LIMIT];
memset(Sieve,1,LIMIT); // initialise all entries to '1'
for(i=n;i<LIMIT;i+=n) {Sieve=0;}
As k gets large this implementation is really slow for small n,
especially if you have to sieve more than one n. Is there a
more efficient way to implement this? Are there fast memory
operators like memset in c++ for this task?
Thanks for your help!
Best,
Oswald Kluge