Sieve of Eratosthenes

Ramon Leon ramon.leon at allresnet.com
Mon Oct 9 21:21:46 UTC 2006


> -----Original Message-----
> From: squeak-dev-bounces at lists.squeakfoundation.org 
> [mailto:squeak-dev-bounces at lists.squeakfoundation.org] On 
> Behalf Of Davide Varvello
> Sent: Monday, October 09, 2006 1:53 PM
> To: The general-purpose Squeak developers list
> Subject: Sieve of Eratosthenes
> 
> Hi All,
> I did some performance tests comparing java and squeak. The 
> java code is this:
> public class GeneratePrimes {
> 	public static double generate(int n) {
> 		long start = System.currentTimeMillis();
> 		boolean sieve[] = new boolean[n];
> 		Arrays.fill(sieve, true);
> 		sieve[0] = false;
> 		sieve[1] = false;
> 		for (int i = 2; i < n; i++) {
> 			if (sieve[i]) {
> 				for (int j = 2 * i; j < n; j += i) {
> 					sieve[j] = false;
> 				}
> 			}
> 		}
> 
> 		return (System.currentTimeMillis() - start);
> 	}
> 
> The Squeak one is:
> 
> runOn: aNumber 
> 	| sieve |
> 
> 	sieve := Array new: aNumber withAll: true.
> 	sieve at: 1 put: false.
> 
> 	(2 to: aNumber) do: [:i | (sieve at: i) ifTrue: [(i to: 
> aNumber by: i) do: [:k | sieve at: k put: false] ]
> 
> The Squeak code is better (of course) but on a number of 
> 1000000 Java spends 94 msec instead Squeak 2650!
> Am I using the right approach or should I change something in 
> my squeak code to make it perform better (but preserving clearness)?

Here's my implementation, it's a little faster, but not much.

Integer>>sieveOfEratosthenes
	"generates primes up to self, educational algorithm, not for
production use"
	| primes |
	primes := ByteArray new: self.
	2 to: self do: [:each | 
		(primes at: each) = 0 ifTrue: [each + each to: self
			by: each do: [:notPrime | 
						primes at: notPrime put:
1]]].
	^(2 to: self) select: [:each | (primes at: each) = 0]





More information about the Squeak-dev mailing list