#Includes code from
#http://rosettacode.org/wiki/Prime_decomposition
#and http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/

require "prime"

def prime(a)
  if a == 2
    true
  elsif a <= 1 || a % 2 == 0
    false
  else
    divisors = (3..Math.sqrt(a)).step(2)
    divisors.none? { |d| a % d == 0 }
  end
end

def prime_factors(i)
  factors = []
  check = proc do |p|
    while(q, r = i.divmod(p)
          r.zero?)
      factors << p
      i = q
    end
  end
  check[2]
  check[3]
  p = 5
  while p * p <= i
    check[p]
    p += 2
    check[p]
    p += 4    # skip multiples of 2 and 3
  end
  factors << i if i > 1
  factors
end
 
def primes(limit)
  (enclose = lambda { |primes|
    primes.last.succ.upto(limit) do |trial_pri|
      if primes.none? { |pri| (trial_pri % pri).zero? }
        return enclose.call(primes << trial_pri)
      end
    end
    primes
  }).call([2])
end
 
def next_prime(n)
    r=n+1
    while not prime(r)
      r += 1
    end
    r
end

class Array
  def powerSet!
    return [[]] if empty?()
    f = shift()
    rec = powerSet!
    return rec + rec.collect {|i| [f] + i }
  end

  def powerSet
    return clone().powerSet!
  end
end

def prod_plus_one_(w) #For inner arrays.
  z=1
  for x in w
     z *= x
  end
  prime_factors(z+1)
end

def prod_plus_one(v) #For outer array.
  z=[]
  for w in v
    z += prod_plus_one_(w)
  end
return z.uniq
end

def factorize(v) #Factorize vector to list of primes
  z=[]
  for i in v
     z += prime_factors(i)
  end
z.uniq.sort
end

def is_in(a,v)
    t=false
    for i in v
      if i==a then
       t=true
       break
      end
    end
    t
end

def get_next(v)
    x=0
    a=v[-1]
    while x==0        
        a=next_prime(a)
        p=factorize(prod_plus_one(v.powerSet))
        if not is_in(a,p) then
          x=1
          break
        end
    end
    a 
end

def first(m)
  v=[2]
  for i in 2..m
    v << get_next(v)
  end
  v
end


print first(20)