[Pkg] The Trunk: Kernel-ul.597.mcz
commits at source.squeak.org
commits at source.squeak.org
Thu Jun 16 22:47:35 UTC 2011
Levente Uzonyi uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-ul.597.mcz
==================== Summary ====================
Name: Kernel-ul.597
Author: ul
Time: 17 June 2011, 12:38:04.174 am
UUID: 579dc488-9b22-5f4c-8a32-d60e5a1f2032
Ancestors: Kernel-ul.596
A more efficient implementation of Integer class >> #primesUpTo:do: using the Sieve of Eratosthenes.
=============== Diff against Kernel-ul.596 ===============
Item was changed:
----- Method: Integer class>>primesUpTo:do: (in category 'prime numbers') -----
primesUpTo: max do: aBlock
"Compute aBlock with all prime integers up to the given integer."
"Integer primesUpTo: 100"
+ | index limit limitSqrtFloor sieve |
+ limit := max asInteger.
+ limit <= 1 ifTrue: [ ^self ].
- | limit flags prime k |
- limit := max asInteger - 1.
"Fall back into #largePrimesUpTo:do: if we'd require more than 100k of memory;
the alternative will only requre 1/154th of the amount we need here and is almost as fast."
+ limit > 25000 ifTrue:[ ^self largePrimesUpTo: limit do: aBlock ].
+ limit := limit - 1. "upTo:"
+ sieve := Array new: limit withAll: true.
+ sieve at: 1 put: false.
+ index := 2.
+ limitSqrtFloor := limit sqrtFloor.
+ [ index <= limitSqrtFloor ] whileTrue: [
+ (sieve at: index) ifTrue: [
+ | notPrimeIndex |
+ aBlock value: index.
+ notPrimeIndex := index * index.
+ [ notPrimeIndex <= limit ] whileTrue: [
+ sieve at: notPrimeIndex put: false.
+ notPrimeIndex := notPrimeIndex + index ] ].
+ index := index + 1 ].
+ [ index <= limit ] whileTrue: [
+ (sieve at: index) ifTrue: [
+ aBlock value: index ].
+ index := index + 1 ]
+ !
- limit > 25000 ifTrue:[^self largePrimesUpTo: max do: aBlock].
- flags := (Array new: limit) atAllPut: true.
- 1 to: limit - 1 do: [:i |
- (flags at: i) ifTrue: [
- prime := i + 1.
- k := i + prime.
- [k <= limit] whileTrue: [
- flags at: k put: false.
- k := k + prime].
- aBlock value: prime]].
- !
More information about the Packages
mailing list