int Fibonacci(int n) {
 int a = 1, b = 1, c, i;
 for (i=3; i<=n; i++) {c = b; b += a; a = c; }
 return b;
}

int factorial(int x) {
 int fac = 1;
 for (int i=2; i<=x; i++) fac *= i;
 return fac;
}

#define nCr(n, r) (factorial(n) / factorial(n-r) / factorial(r))
#define nPr(n, r) (factorial(n) / factorial(n-r))

int modInverse(int a, int n) {
 int i = n, v = 0, d = 1;
 while (a>0) {
  int t = i/a, x = a;
  a = i % x;
  i = x;
  x = d;
  d = v - t*x;
  v = x;
 }
 v %= n;
 if (v<0) v = (v+n)%n;
 return v;
}

int gcd(int x, int y) {
 int a, b;
 if (x<y) {a = y; b = x; }
 else if (x>y) {a = x; b = y; }
 else {return x; }
 do {
  int r = a % b;
  a = b;
  b = r;
 } while (b != 0);
 return a;
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char** argv) {
 int qty = (argc > 1) ? (int) strtol(argv[1], NULL, 10) : 100;
 if (qty < 3) qty = 100;
 unsigned int primes[qty];
 primes[0] = 2U; primes[1] = 3U;
 printf("2\n3\n");
 for (int i=2; i<qty; i++) {
  int j = primes[i-1];
  iter: j += 2U;
  unsigned bound = (unsigned) sqrt((double) j);
  for (int k=1; k<i; k++) {
   if (primes[k] > bound) break; /*Not a viable shortcut for small quantities*/
   if (!(j % primes[k])) goto iter;
  }
  primes[i] = j;
  printf("%u\n", j);
 }
 return 0;
}

max = Integer(ARGV.shift || 100)
	
sieve = [nil, nil] + (2 .. max).to_a
	
(2 .. Math.sqrt(max)).each do |i|
  next unless sieve[i]
  (i*i).step(max, i) do |j|
    sieve[j] = nil
  end
end
	
puts sieve.compact.join(", ")



#------------------------------------



#!/usr/local/bin/ruby -w

require 'benchmark' 

class Integer

   def primes1

      primes = [nil, nil].concat((2..self).to_a)

      (2 .. Math.sqrt(self).floor).each do |i|
         next unless primes[i]
            (i*i).step(self, i) do |j|
               primes[j] = nil
            end
      end
	
      primes.compact!

   end  


   def primes2

      sieve = []
      3.step(self, 2) { |i| sieve[i] = i }
      sieve[1] = nil
      sieve[2] = 2

      3.step(Math.sqrt(self).floor, 2) do |i| 
         next unless sieve[i]
         (i*i).step(self, i) do |j|
            sieve[j] = nil
         end
      end

      sieve.compact!

   end 


   def primes3

      n2 = 0
      i = 0
      sieve = []

      while n2 < self
         n1 = 6*i+1       # cf. http://betterexplained.com/articles/another-look-at-prime-numbers/ and
         n2 = n1+4        # http://everything2.com/index.pl?node_id=1176369
         i += 1

         sieve[n1] = n1
         sieve[n2] = n2

      end  

      sieve[1] = nil
      sieve[2] = 2
      sieve[3] = 3
      sieve[-1] = nil

      5.step(Math.sqrt(self).floor, 2) do |i| 
         next unless sieve[i]
         (i*i).step(self, i) do |j|     
            sieve[j] = nil
         end
      end   

      sieve.compact!

   end 

end



limit = 10_000_000
limit = 5_000_000
limit = 1_000_000
limit = 500_000
limit = 100_000
limit = 10_000
limit = 7_500
limit = 5_000
limit = 1_000
limit = 500_000

ret1 = nil
ret2 = nil
ret3 = nil

# cf. primegen.c, http://cr.yp.to/primegen.html and
# prime_sieve.c, http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html

Benchmark.bm(14) do |t|       

   t.report("primes up to #{limit}: ") do
      ret1 = limit.primes1
   end 

   t.report("primes up to #{limit}: ") do
      ret2 = limit.primes2
   end 

   t.report("primes up to #{limit}: ") do
      ret3 = limit.primes3
   end 


end 


puts

#p ret1.first(10)
p ret1.last(10)
p ret1.size

puts

#p ret2.first(10)
p ret2.last(10)
p ret2.size

puts 

#p ret3.first(10)
p ret3.last(10)
p ret3.size

class Integer
  FibonacciCache = Hash.new do |hash, key|
    if hash.has_key?(key - 1) and hash.has_key?(key - 2)
      hash[key] = hash[key - 1] + hash[key - 2]
    elsif hash.has_key?(key + 1) and hash.has_key?(key + 2)
      hash[key] = hash[key + 2] - hash[key + 1]
    else
      subkey = key.div(2)
      case key.modulo(4)
        when 1
          hash[key] = (2*hash[subkey] + hash[subkey - 1])*(2*hash[subkey] - hash[subkey - 1]) + 2
        when 3
          hash[key] = (2*hash[subkey] + hash[subkey - 1])*(2*hash[subkey] - hash[subkey - 1]) - 2
        else
          hash[key] = hash[subkey] * (hash[subkey] + 2*hash[subkey - 1])
      end
    end
  end
  FibonacciCache[0] = 0
  FibonacciCache[1] = 1

  def fib
    return FibonacciCache[self]
  end

  def fib_uncached
    return FibonacciCache.dup[self]
  end
end

start_time = Time.now
1_000_000.fib
#fibs = (5..10).map { |i| i.fib }
#fibs = (1..100000).map { |i| i.fib }
#puts fibs.size
#puts fibs.last
p Time.now - start_time

puts "Doesn't work !" unless (1..10).map { |i| i.fib } == [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]


#-----------------------------------------------------------------------


# From: http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/37727
# Author: Shin-ichiro HARA


  class QR3
    attr_reader :a, :b

    def inspect
      "{#{@a},#{@b}}"
    end
    alias to_s inspect

    def initialize(a, b)
      @a, @b = a, b
    end

    def *(r)
      u = (@a + @b)*(r.a + r.b)
      v = (@a - @b)*(r.a - r.b)
      QR3.new((u + v)>>1, @b*r.b + ((u - v)>>1))
    end

    def **(n)
      if n == 0
        QR3.new(1, 0)
      elsif n > 0
        z = x = self
        n -= 1
        while (z*= x if n[0].nonzero?; (n >>= 1).nonzero?)
          x *= x
        end
        z
      end
    end
  end

  def fib_qr3(n)
    (QR3.new(0, 1)**n).b
  end

n = 1000

start_time = Time.now
fib_qr3(n)
p Time.now - start_time

$cache = {}

def parts(s,u)
  u0 = [s,u].min
  if u0 < 1
    []
  else
    i = (s-1)*s/2+u0-1
    $cache[i] ||
    begin
      a = []
      u0.downto(1) do |n|
        r = s - n
        if (r > 0)
          parts(r,n).each do |elem|
            a.push([n, elem])
          end
        else
          a.push([n])
        end
      end
      $cache[i] = a
      a
    end
  end
end

def part(n)
  parts(n,n).map{|x| x.flatten}
end

p part(5)     #=> [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

def perm(l):
    sz = len(l)
    if sz <= 1:
        return [l]
    return [p[:i]+[l[0]]+p[i:] for i in xrange(sz) for p in perm(l[1:])]

combine([1,2]) == [[1], [2], [1,2]];

var combine = function(a) {
  var fn = function(n, src, got, all) {
    if (n == 0) {
      if (got.length > 0) {
        all[all.length] = got;
      }
      return;
    }
    for (var j = 0; j < src.length; j++) {
      fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
    }
    return;
  }
  var all = [];
  for (var i=0; i < a.length; i++) {
    fn(i, a, [], all);
  }
  all.push(a);
  return all;
}