--- a/Integer.st Wed Sep 16 14:32:43 2009 +0200
+++ b/Integer.st Wed Sep 16 16:04:57 2009 +0200
@@ -2979,34 +2979,34 @@
rest := self.
limit := (rest // 2).
limitArgOrNil notNil ifTrue:[
- limit := limit min:limitArgOrNil.
+ limit := limit min:limitArgOrNil.
].
"/ try to get the number down fast:
n := rest lowBit.
n ~~ 1 ifTrue:[
- self == 2 ifTrue:[^ #() ].
- factors add:2 withOccurrences:(n-1).
- rest := rest rightShift:(n-1).
+ self == 2 ifTrue:[^ #() ].
+ factors add:2 withOccurrences:(n-1).
+ rest := rest rightShift:(n-1).
].
checkThisFactor := [:prime |
- prime*prime > rest ifTrue:[
- (rest ~~ 1 and:[factors notEmpty]) ifTrue:[ factors add:rest ].
- ^ factors.
- ].
-
- [rest \\ prime == 0] whileTrue:[
- factors add:prime.
- rest := rest // prime.
- rest == 1 ifTrue:[^ factors].
- ].
- lastPrime := prime.
- ].
+ prime*prime > rest ifTrue:[
+ (rest ~~ 1 and:[factors notEmpty]) ifTrue:[ factors add:rest ].
+ ^ factors.
+ ].
+
+ [rest \\ prime == 0] whileTrue:[
+ factors add:prime.
+ rest := rest // prime.
+ rest == 1 ifTrue:[^ factors].
+ ].
+ lastPrime := prime.
+ ].
limit <= 2000 ifTrue:[
- Integer primesUpTo2000 do:checkThisFactor.
- ^ factors
+ Integer primesUpTo2000 do:checkThisFactor.
+ ^ factors
].
"/ actually, all of the code is duplicated; once for primes from a table,
@@ -3015,41 +3015,41 @@
"/ (the primesUpTo uses a faster sieve, but can only represent primes to upTo (say)
"/ a few millions.
- Integer primesUpTo:(limit min:1000000) do:checkThisFactor.
+ Integer primesUpTo:(limit min:(1000000 max:Integer primeCacheSize)) do:checkThisFactor.
nextTry := lastPrime + 2.
[ nextTry <= limit ] whileTrue:[
- "/ now, we are beyond the list of pre-generated primes.
- "/ change our strategy to: see if it divides an odd number;
- "/ if so, add the divisor's prime factors.
- nextTry*nextTry > rest ifTrue:[
- (rest ~~ 1 and:[factors notEmpty]) ifTrue:[ factors add:rest ].
- ^ factors.
- ].
- [(rest \\ nextTry) == 0] whileTrue:[
- "/ can only happen relatively late after the last prime,
- "/ because otherwise, the primeFactors of nextTry would already have
- "/ been found as divisors.
- "/ first chance is: (lastPrime + 2) squared
- nextTry < lastPrime squared ifTrue:[
- "/ nextTry is a prime !!
- factors add:nextTry
- ] ifFalse:[
- factors addAll:(nextTry primeFactors).
- ].
- rest := rest // nextTry.
- ].
- nextTry := nextTry + 2.
+ "/ now, we are beyond the list of pre-generated primes.
+ "/ change our strategy to: see if it divides an odd number;
+ "/ if so, add the divisor's prime factors.
+ nextTry*nextTry > rest ifTrue:[
+ (rest ~~ 1 and:[factors notEmpty]) ifTrue:[ factors add:rest ].
+ ^ factors.
+ ].
+ [(rest \\ nextTry) == 0] whileTrue:[
+ "/ can only happen relatively late after the last prime,
+ "/ because otherwise, the primeFactors of nextTry would already have
+ "/ been found as divisors.
+ "/ first chance is: (lastPrime + 2) squared
+ nextTry < lastPrime squared ifTrue:[
+ "/ nextTry is a prime !!
+ factors add:nextTry
+ ] ifFalse:[
+ factors addAll:(nextTry primeFactors).
+ ].
+ rest := rest // nextTry.
+ ].
+ nextTry := nextTry + 2.
].
^ factors
"
2 to:10000 do:[:n |
- self assert:((n isPrime and:[ n primeFactors isEmpty])
- or:[ n isPrime not and:[n primeFactors product = n]])
+ self assert:((n isPrime and:[ n primeFactors isEmpty])
+ or:[ n isPrime not and:[n primeFactors product = n]])
]
3 to:10000 do:[:n |
- self assert:(n factorial primeFactors product = n factorial)
+ self assert:(n factorial primeFactors product = n factorial)
]
13195 primeFactors
@@ -3070,9 +3070,9 @@
1000000000 primeFactors
Time millisecondsToRun:[
- 1000 timesRepeat:[
- 10000000000000000000000000000000000000 primeFactors
- ]
+ 1000 timesRepeat:[
+ 10000000000000000000000000000000000000 primeFactors
+ ]
] 421
"
!
@@ -4208,7 +4208,7 @@
!Integer class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.226 2009-09-16 11:51:31 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.227 2009-09-16 14:04:57 cg Exp $'
! !
Integer initialize!