fork download 
  1. | count |
  2. count := 0.
  3. Integer primesUpTo: 1e10 do: [:prime | count := count + 1].
  4. count '=> 455052511 '
  5.  
  6. --
  7.  
  8. Integer class >> primesUpTo: max do: aBlock
  9.    "Compute aBlock with all prime integers up to the given integer."
  10.    "Integer primesUpTo: 100"
  11.  
  12.    | limit flags prime k |
  13.    limit := max asInteger - 1.
  14.    "Fall back into #largePrimesUpTo:do: if we'd require more than 100k of memory; 
  15.    the alternative will only requre 1/154th of the amount we need here and is almost as fast."
  16.    limit > 25000 ifTrue:[^self largePrimesUpTo: max do: aBlock].
  17.    flags := (Array new: limit) atAllPut: true.
  18.    1 to: limit - 1 do: [:i |
  19.       (flags at: i) ifTrue: [
  20.          prime := i + 1.
  21.          k := i + prime.
  22.          [k <= limit] whileTrue: [
  23.             flags at: k put: false.
  24.             k := k + prime].
  25.          aBlock value: prime]].
  26.  
  27. --
  28.  
  29. Integer class >> largePrimesUpTo: max do: aBlock
  30.    "Evaluate aBlock with all primes up to maxValue.
  31.    The Algorithm is adapted from http://w...content-available-to-author-only...k.com/~jrm/printprimes.html
  32.    It encodes prime numbers much more compactly than #primesUpTo: 
  33.    38.5 integer per byte (2310 numbers per 60 byte) allow for some fun large primes.
  34.    (all primes up to SmallInteger maxVal can be computed within ~27MB of memory;
  35.    the regular #primesUpTo: would require 4 *GIGA*bytes).
  36.    Note: The algorithm could be re-written to produce the first primes (which require
  37.    the longest time to sieve) faster but only at the cost of clarity."
  38.  
  39.    | limit flags maskBitIndex bitIndex maskBit byteIndex index primesUpTo2310 indexLimit |
  40.    limit := max asInteger - 1.
  41.    indexLimit := max sqrt truncated + 1.
  42.    "Create the array of flags."
  43.    flags := ByteArray new: (limit + 2309) // 2310 * 60 + 60.
  44.    flags atAllPut: 16rFF. "set all to true"
  45.  
  46.    "Compute the primes up to 2310"
  47.    primesUpTo2310 := self primesUpTo: 2310.
  48.  
  49.    "Create a mapping from 2310 integers to 480 bits (60 byte)"
  50.    maskBitIndex := Array new: 2310.
  51.    bitIndex := -1. "for pre-increment"
  52.    maskBitIndex at: 1 put: (bitIndex := bitIndex + 1).
  53.    maskBitIndex at: 2 put: (bitIndex := bitIndex + 1).
  54.  
  55.    1 to: 5 do:[:i| aBlock value: (primesUpTo2310 at: i)].
  56.  
  57.    index := 6.
  58.    2 to: 2309 do:[:n|
  59.       [(primesUpTo2310 at: index) < n] 
  60.          whileTrue:[index := index + 1].
  61.       n = (primesUpTo2310 at: index) ifTrue:[
  62.          maskBitIndex at: n+1 put: (bitIndex := bitIndex + 1).
  63.       ] ifFalse:[
  64.          "if modulo any of the prime factors of 2310, then could not be prime"
  65.          (n \\ 2 = 0 or:[n \\ 3 = 0 or:[n \\ 5 = 0 or:[n \\ 7 = 0 or:[n \\ 11 = 0]]]]) 
  66.             ifTrue:[maskBitIndex at: n+1 put: 0]
  67.             ifFalse:[maskBitIndex at: n+1 put: (bitIndex := bitIndex + 1)].
  68.       ].
  69.    ].
  70.  
  71.    "Now the real work begins...
  72.    Start with 13 since multiples of 2,3,5,7,11 are handled by the storage method;
  73.    increment by 2 for odd numbers only."
  74.    13 to: limit by: 2 do:[:n|
  75.       (maskBit := maskBitIndex at: (n \\ 2310 + 1)) = 0 ifFalse:["not a multiple of 2,3,5,7,11"
  76.          byteIndex := n // 2310 * 60 + (maskBit-1 bitShift: -3) + 1.
  77.          bitIndex := 1 bitShift: (maskBit bitAnd: 7).
  78.          ((flags at: byteIndex) bitAnd: bitIndex) = 0 ifFalse:["not marked -- n is prime"
  79.             aBlock value: n.
  80.             "Start with n*n since any integer < n has already been sieved 
  81.             (e.g., any multiple of n with a number k < n has been cleared 
  82.             when k was sieved); add 2 * i to avoid even numbers and
  83.             mark all multiples of this prime. Note: n < indexLimit below
  84.             limits running into LargeInts -- nothing more."
  85.             n < indexLimit ifTrue:[
  86.                index := n * n.
  87.                (index bitAnd: 1) = 0 ifTrue:[index := index + n].
  88.                [index <= limit] whileTrue:[
  89.                   (maskBit := maskBitIndex at: (index \\ 2310 + 1)) = 0 ifFalse:[
  90.                      byteIndex := (index // 2310 * 60) + (maskBit-1 bitShift: -3) + 1.
  91.                      maskBit := 255 - (1 bitShift: (maskBit bitAnd: 7)).
  92.                      flags at: byteIndex put: ((flags at: byteIndex) bitAnd: maskBit).
  93.                   ].
  94.                   index := index + (2 * n)].
  95.             ].
  96.          ].
  97.       ].
  98.    ].
  99.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/zKMZYx
language:
Text (text 6.10)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!