tests/bench_nsieve_bool.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 fun nsieve(n: Int): Int
  18 do
  19         var count = n-2
  20         var array = new Array[Bool].with_capacity(n)
  21         for i in [0..n[ do
  22                 array.add(true)
  23         end
  24         for i in [2..n[ do
  25                 if array[i] then
  26                         var j = i * 2
  27                         while j < n do
  28                                 if array[j] then
  29                                         array[j] = false
  30                                         count = count - 1
  31                                 end
  32                                 j = j + i
  33                         end
  34                 end
  35         end
  36         return count
  37 end
  38
  39 fun test(n: Int)
  40 do
  41         var m = 10000.lshift(n)
  42         print("Primes up to {m} {nsieve(m)}")
  43 end
  44
  45 var n = 2
  46 if args.length == 1 then
  47         n = args.first.to_i
  48 end
  49
  50 test(n)
  51 if n >= 1 then
  52         test(n-1)
  53 end
  54 if n >= 2 then
  55         test(n-2)
  56 end