tests/shootout_nsieve.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2005-2008 Jean Privat <jean@pryen.org>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 import c
  18
  19 class Bitarray
  20
  21         var narr: CByteArray
  22
  23         init do
  24                 for x in [0 .. narr.length[ do narr[x] = 0xFFu8
  25         end
  26
  27         fun [](pos: Int): Bool do
  28                 pos -= 2
  29                 return (narr[pos / 8] & (1u8 << (7 - pos % 8))) != 0u8
  30         end
  31
  32         fun []=(pos: Int, val: Bool) do
  33                 pos -= 2
  34                 if val then
  35                         narr[pos / 8] |= 1u8 << (7 - pos % 8)
  36                 else
  37                         narr[pos / 8] &= 0xFFu8 - (1u8 << (7 - pos % 8))
  38                 end
  39         end
  40 end
  41
  42 fun nsieve(n: Int): Int
  43 do
  44         var count = 0
  45         var b_arrsz = ((n - 1).to_f / 8.0).ceil.to_i
  46         var bitarr = new Bitarray(new CByteArray(b_arrsz))
  47         for i in [2 .. n[ do
  48                 # If self is already false, then no need to check for multiples
  49                 if not bitarr[i] then continue
  50                 count += 1
  51                 var j = i * i
  52                 while j < n do
  53                         bitarr[j] = false
  54                         j += i
  55                 end
  56         end
  57         return count
  58 end
  59
  60 fun test(n: Int)
  61 do
  62         var m = 10000 << n
  63         print("Primes up to {m} {nsieve(m)}")
  64 end
  65
  66 var n = 2
  67 if args.length == 1 then
  68         n = args.first.to_i
  69 end
  70
  71 test(n)
  72 if n >= 1 then
  73         test(n-1)
  74 end
  75 if n >= 2 then
  76         test(n-2)
  77 end