#! /usr/bin/ruby

require 'set'

def genprimes(mx)
  primesh=Set.new([2,3])
  (6..mx+1).step(6) do |i|
    (i-1..i+1).step(2) do |j|
      if j <= mx then
        primesh.add(j)
      end
    end
  end
  q=[2,3,5,7]
  p=q.shift
  mr=Integer.sqrt(mx)
  while p <= mr do
    if primesh.include?(p)
      (p*p..mx).step(p) do |i|
        primesh.delete?(i)
      end
    end
    if q.length<2 then
      q.push(q[-1]+4)
      q.push(q[-1]+2)
    end
    p=q.shift
  end
  return primesh.each.sort
end

def squarefree(max)
  out=[]
  primes=genprimes(Integer.sqrt(max))
  plimit=1
  1.upto(max) do |candidate|
    squarefree=true
    while plimit * plimit < candidate do
      plimit += 1
    end
    cc=candidate
    primes.each do |pr|
      if pr > plimit then
        break
      end
      n=0
      while cc % pr == 0 do
        n += 1
        if n > 1 then
          squarefree=false
          break
        end
        cc=(cc/pr).to_i
      end
      if !squarefree then
        break
      end
    end
    if squarefree then
      out.push(candidate)
    end
  end
  return out
end

require 'test/unit'

class TestSquarefree < Test::Unit::TestCase

  def test_ex1
    assert_equal([1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21,
                  22, 23, 26, 29, 30],squarefree(30))
  end

  def test_ex2
    assert_equal([1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21,
                  22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42,
                  43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67,
                  69, 70, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89,
                  91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107, 109,
                  110, 111, 113],squarefree(113))
  end

  def test_ex3
    assert_equal([1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21,
                  22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42,
                  43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67,
                  69, 70, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89,
                  91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107, 109,
                  110, 111, 113, 114, 115, 118, 119, 122, 123, 127, 129,
                  130, 131, 133, 134, 137, 138, 139, 141, 142, 143, 145,
                  146, 149, 151, 154, 155, 157, 158, 159, 161, 163, 165,
                  166, 167, 170, 173, 174, 177, 178, 179, 181, 182, 183,
                  185, 186, 187, 190, 191, 193, 194, 195, 197, 199, 201,
                  202, 203, 205, 206, 209, 210, 211, 213, 214, 215, 217,
                  218, 219, 221, 222, 223, 226, 227, 229, 230, 231, 233,
                  235, 237, 238, 239, 241, 246, 247, 249, 251, 253, 254,
                  255, 257, 258, 259, 262, 263, 265, 266, 267, 269, 271,
                  273, 274, 277, 278, 281, 282, 283, 285, 286, 287, 290,
                  291, 293, 295, 298, 299, 301, 302, 303, 305, 307, 309,
                  310, 311, 313, 314, 317, 318, 319, 321, 322, 323, 326,
                  327, 329, 330, 331, 334, 335, 337, 339, 341, 345, 346,
                  347, 349, 353, 354, 355, 357, 358, 359, 362, 365, 366,
                  367, 370, 371, 373, 374, 377, 379, 381, 382, 383, 385,
                  386, 389, 390, 391, 393, 394, 395, 397, 398, 399, 401,
                  402, 403, 406, 407, 409, 410, 411, 413, 415, 417, 418,
                  419, 421, 422, 426, 427, 429, 430, 431, 433, 434, 435,
                  437, 438, 439, 442, 443, 445, 446, 447, 449, 451, 453,
                  454, 455, 457, 458, 461, 462, 463, 465, 466, 467, 469,
                  470, 471, 473, 474, 478, 479, 481, 482, 483, 485, 487,
                  489, 491, 493, 494, 497, 498, 499],squarefree(500))
  end

end