efficient prime algorithm in ruby(sieve of eratosthenes)....
  '''author -> shivamzaz @imsec
   tag -> effiecient prime finfinding algorithms
   complexity -> O(n loglog n)
   level -> cake walk'''
p=gets().to_i
prm=[]
for i in 0..p
    prm[i]=1
end
prm[0]=0
prm[1]=0
for i in 2..(Math.sqrt(p)).floor
    if(prm[i]==1)
        j=2
        while((i*j)<=p);    # coz table started from j->2
            prm[i*j]=0
            j+=1
        end
    end
end
for i in 0..p
    if(prm[i]==1)
        puts i
    end
end
'''
output:
    15
    2
    3
    5
    7
    11
    13
'''