--- a/Integer.st Sat Aug 14 12:56:21 2010 +0200
+++ b/Integer.st Tue Aug 17 17:27:46 2010 +0200
@@ -1139,6 +1139,7 @@
^ self == Integer
! !
+
!Integer methodsFor:'Compatibility-Dolphin'!
& aNumber
@@ -3059,18 +3060,17 @@
primeFactors
"return a collection of prime factors of the receiver.
For prime numbers, an empty collection is returned.
- Can take a long time for big numbers
- (win a nobel price, if you find something quick)"
+ Can take a long time for big numbers"
^ self primeFactorsUpTo:nil
"
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
@@ -3091,18 +3091,22 @@
1000000000 primeFactors
Time millisecondsToRun:[
- 1000 timesRepeat:[
- 10000000000000000000000000000000000000 primeFactors
- ]
+ 1000 timesRepeat:[
+ 10000000000000000000000000000000000000 primeFactors
+ ]
] 421
"
+
+ "Modified: / 17-08-2010 / 17:27:33 / cg"
!
primeFactorsUpTo:limitArgOrNil
"return a collection of prime factors of the receiver.
For prime numbers, an empty collection is returned.
Can take a long time for big numbers
- (win a nobel price, if you find something quick)"
+ (win a nobel price, if you find something quick (*)
+
+ (*):which does not mean that the code below is optimal - far from it !!"
|rest n factors limit lastPrime checkThisFactor nextTry|
@@ -3110,34 +3114,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,
@@ -3150,37 +3154,37 @@
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
@@ -3201,11 +3205,13 @@
1000000000 primeFactors
Time millisecondsToRun:[
- 1000 timesRepeat:[
- 10000000000000000000000000000000000000 primeFactors
- ]
+ 1000 timesRepeat:[
+ 10000000000000000000000000000000000000 primeFactors
+ ]
] 421
"
+
+ "Modified: / 17-08-2010 / 17:27:24 / cg"
!
raisedTo:exp mod:mod
@@ -3929,6 +3935,7 @@
"Modified: 15.10.1997 / 18:43:49 / cg"
! !
+
!Integer methodsFor:'special access'!
exponent
@@ -4707,11 +4714,11 @@
!Integer class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.248 2010-08-02 10:34:20 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.249 2010-08-17 15:27:46 cg Exp $'
!
version_CVS
- ^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.248 2010-08-02 10:34:20 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/Integer.st,v 1.249 2010-08-17 15:27:46 cg Exp $'
! !
Integer initialize!