Vasya and Petya are playing a simple game. Vasya thought of number x between 1 and n, and Petya tries to guess the number.

Petya can ask questions like: "Is the unknown number divisible by number y?".

The game is played by the following rules: first Petya asks all the questions that interest him (also, he can ask no questions), and then Vasya responds to each question with a 'yes' or a 'no'. After receiving all the answers Petya should determine the number that Vasya thought of.

Unfortunately, Petya is not familiar with the number theory. Help him find the minimum number of questions he should ask to make a guaranteed guess of Vasya's number, and the numbers y_{i}, he should ask the questions about.


-----Input-----

A single line contains number n (1 ≤ n ≤ 10^3).


-----Output-----

Print the length of the sequence of questions k (0 ≤ k ≤ n), followed by k numbers — the questions y_{i} (1 ≤ y_{i} ≤ n).

If there are several correct sequences of questions of the minimum length, you are allowed to print any of them.


-----Examples-----
Input
4

Output
3
2 4 3 

Input
6

Output
4
2 4 3 5 



-----Note-----

The sequence from the answer to the first sample test is actually correct.

If the unknown number is not divisible by one of the sequence numbers, it is equal to 1.

If the unknown number is divisible by 4, it is 4.

If the unknown number is divisible by 3, then the unknown number is 3.

Otherwise, it is equal to 2. Therefore, the sequence of questions allows you to guess the unknown number. It can be shown that there is no correct sequence of questions of length 2 or shorter.

Difficulty: competition

Starter code:

Solutions:
def main():
    n = int(input())
    result = []
    for i in range(2, n + 1):
        j = 2
        while j * j <= i:
            if i % j == 0:
                break
            j += 1
        else:
            j = i
            while j <= n:
                result.append(j)
                j *= i
    
    print(len(result))
    print(' '.join(str(i) for i in result))
    
    
    
main()


n = int(input())

def is_prime(x):
    if x == 2:
        return True
    if x == 1 or x % 2 == 0:
        return False
    i = 3
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

ans = []
for i in range(2, n + 1):
    if is_prime(i):
        j = i
        while j <= n:
            ans.append(j)
            j *= i

print(len(ans))
print(' '.join(map(str, ans)))


n = int(input())

p = [True for _ in range(n + 1)]

l = []

for i in range(2, n + 1):
    if not p[i]:
        continue
    for j in range(i, n + 1, i):
        p[j] = False
    
    a = i
    while a <= n:
        l.append(a)
        a *= i

print(len(l))
for i in l:
    print(i, end=" ")
print()

import math
import array
def is_prime(x):
    i = 2
    while(i <= math.sqrt(x)):
        if(x % i == 0):
            return False
        i = i + 1
    return True
prime = [False for c in range(1000)]
n = int(input())
i = 2
answer = 0
while(i <= n):
    if(prime[i - 1] == True):
        i = i + 1
        continue
    if(is_prime(i)):
        answer = answer + 1
        prime[i - 1] = True
        j = i*i
        while(j <= n):
            prime[j - 1] = True
            answer = answer + 1
            j = j * i
    i = i + 1
i = 2
print(answer)
while(i <= n):
    if(prime[i - 1]):
        print(i, end = ' ')
    i = i + 1
    
        
                
        
        


import math
import array
def is_prime(x):
    i = 2
    while(i <= math.sqrt(x)):
        if(x % i == 0):
            return False
        i = i + 1
    return True
primel = [0 for c in range(1000)]
prime = array.array('i', primel)
n = int(input())
i = 2
answer = 0
while(i <= n):
    if(prime[i - 1] == 1):
        i = i + 1
        continue
    if(is_prime(i)):
        answer = answer + 1
        prime[i - 1] = 1
        j = i*i
        while(j <= n):
            prime[j - 1] = 1
            answer = answer + 1
            j = j * i
    i = i + 1
i = 2
print(answer)
while(i <= n):
    if(prime[i - 1]):
        print(i, end = ' ')
    i = i + 1
    
        
                
        
        


import math
import array
def is_prime(x):
    i = 2
    while(i <= math.sqrt(x)):
        if(x % i == 0):
            return False
        i = i + 1
    return True
answer_list = []
primel = [0 for c in range(1000)]
prime = array.array('i', primel)
n = int(input())
i = 2
answer = 0
while(i <= n):
    if(prime[i - 1] == 1):
        i = i + 1
        continue
    if(is_prime(i)):
        answer = answer + 1
        answer_list.append(i)
        prime[i - 1] = 1
        j = i*i
        while(j <= n):
            prime[j - 1] = 1
            answer = answer + 1
            answer_list.append(j)
            j = j * i
    i = i + 1
print(answer)
for x in answer_list:
    print(x, end = ' ')
    
        
                
        
        


import math
import array
def is_prime(x):
    i = 2
    while(i <= math.sqrt(x)):
        if(x % i == 0):
            return False
        i = i + 1
    return True
answer_list = []
n = int(input())
i = 2
answer = 0
while(i <= n):
    if(is_prime(i)):
        answer = answer + 1
        answer_list.append(i)
        j = i*i
        while(j <= n):
            answer = answer + 1
            answer_list.append(j)
            j = j * i
    i = i + 1
print(answer)
for x in answer_list:
    print(x, end = ' ')
    
        
                
        
        


n = int(input())
p = []
for i in range(2,n+1):
    isprime = True
    for j in p:
        if i % j == 0:
            isprime = False
            break
    if isprime:
        p.append(i)
ans = []
for i in p:
    k = 1
    while i ** k <= n:
        ans.append(str(i ** k))
        k += 1
print(len(ans))
print(' '.join(ans))


n = int(input())
if n==1:
	print(0)
	return
elif n==2:
	print(1)
	print(2)
	return

ans = 0
pr = [0] * (n+1)
p = []
end = 1

while end > 0:
	i = 2
	while pr[i] != 0: 
		i += 1
		if i==n+1:
			end = 0
			break
	if i != n+1:
		pr[i] = 1
		p.append(i)
	j = i
	while i+j<=n: 
		i += j
		pr[i] = 2
res = []
for a in p:
	x = a
	while x <= n:
		res.append(x)
		ans += 1
		x *= a

print(ans)
print(*res)


def main():
    n = int(input()) + 1
    a, res = [True] * n, []
    for p in range(2, n):
        if a[p]:
            pp = 1
            while pp * p < n:
                pp *= p
                res.append(pp)
            a[p:n:p] = [False] * ((n - 1) // p)
    print(len(res))
    print(*res)


def __starting_point():
    main()

__starting_point()

prime=[2,3,5,7,11,13]

def create_list(n):
    nonlocal prime
    for x in range(15,n+1,2):
        notPrime=False
        hold=int(x**0.5)+1
        for j in prime:
            if j>hold:
                break
            if x%j==0:
                notPrime=True
                break
        if notPrime==False:
            prime.append(x)

def main():
    nonlocal prime
    mode="filee"
    if mode=="file":f=open("test.txt","r")
    if mode=="file":n=int(f.readline())
    else:n=int(input())
    create_list(n)
    k=[]
    for j in range(len(prime)):
        num=prime[j]
        while num<=n:
            k.append(num)
            num*=prime[j]
        j+=1
    print(len(k))
    for i in k:
        print(i,end=' ')
    if mode=="file":f.close()


def __starting_point():
    main()

__starting_point()

n = int(input())
questions = []
for i in range(2, n + 1):
	if all(i % q != 0 for q in questions):
		x = i
		while x <= n:
			questions.append(x)
			x *= i
print(len(questions))
print(' '.join(str(q) for q in questions))


import math
import collections

def factorize(n):
    ''' returns a list of prime factors of n.
    ex. factorize(24) = [2, 2, 2, 3]
    source: Rossetta code: prime factorization (slightly modified)
    http://rosettacode.org/wiki/Prime_decomposition#Python:_Using_floating_point
    '''
    step = lambda x: 1 + (x<<2) - ((x>>1)<<1)
    maxq = int(math.floor(math.sqrt(n)))
    d = 1
    q = n % 2 == 0 and 2 or 3
    while q <= maxq and n % q != 0:
        q = step(d)
        d += 1
    return q <= maxq and [q] + factorize(n//q) or [n]

def primes2(limit):
    ''' returns a list of prime numbers upto limit.
    source: Rossetta code: Sieve of Eratosthenes
    http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Odds-only_version_of_the_array_sieve_above
    '''
    if limit < 2: return []
    if limit < 3: return [2]
    lmtbf = (limit - 3) // 2
    buf = [True] * (lmtbf + 1)
    for i in range((int(limit ** 0.5) - 3) // 2 + 1):
        if buf[i]:
            p = i + i + 3
            s = p * (i + 1) + i
            buf[s::p] = [False] * ((lmtbf - s) // p + 1)
    return [2] + [i + i + 3 for i, v in enumerate(buf) if v]


n = int(input())

def solve(n):
    if n == 1:
        print(0)
        return
    primes = primes2(n)
    record = {p:0 for p in primes}
    for m in range(2, n+1):
        facs = factorize(m)
        counts = collections.Counter(facs)
        for p, c in counts.items():
            if c > record[p]:
                record[p] = c
    q = sum(record.values())
    print(q)
    nums = []
    for p, c in record.items():
        for i in range(1, c+1):
            nums.append(p**i)
    if q > 0:
        print(*nums)

solve(n)

n = int(input())
prime = [False] * (n + 1)
ans = []
for i in range(2, n + 1):
 if prime[i]:
   continue
 x = i
 while x <= n:
   ans.append(x)
   prime[x] = True
   x *= i
 x = i
 while x <= n:
   prime[x] = True
   x += i   

print(len(ans))
for x in ans:
  print(x, end= " ")
 

n = int(input())

from math import sqrt
a = []
y = ''

if n > 1:
    for i in range (2, n+1):
        k = 0
        for j in range(2, int(sqrt(i))+1):
             if i % j == 0:
                 k = 1
        if k ==0:
            a.append(i)

k = 0
for i in range(len(a)):
    for j in range(1, 10):
        if a[i]**j <= n:
            k = k + 1
            y = y + str(a[i]**j) + ' '


if n == 1:
   print(0)
else:
    print(k)
    print(y)




    


def is_prime(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return False
		i += 1
	return True

def primes():
	i = 2
	while True:
		if is_prime(i):
			yield i
		i += 1

import itertools

n = int(input())
guesses = []
for p in itertools.takewhile(lambda p: p <= n, primes()):
	x = p
	while x <= n:
		guesses.append(x)
		x *= p
print(len(guesses))
print(' '.join(map(str, guesses)))


n=int(input())
if n==1:
    print(0)
    print('')
else:
    a=[]
    for i in range(2,n+1):
        x=i
        p=0
        for j in a:
            if x%j==0:
               p+=1 
            while x%j==0:
                x=x//j
        if x>1 or (x==1 and p==1):
            a.append(i)
    s=str(a[0])
    L=len(a)
    for j in range(1,L):
        s=s+' '+str(a[j])
    print(len(a))
    print(s)
                


import math
import itertools

n = int(input())
primes = [2]
primes_degrees = []
for i in range(3, n + 1):
    for p in itertools.takewhile(lambda x: x <= i ** 0.5, primes):
        if i%p == 0:
            k = i // p
            while k > 1:
                if k%p != 0: break
                k = k // p
            else:
                primes_degrees.append(i)
            break
    else:
        primes.append(i)

if n == 1:
    print(0)
else:
    print(len(primes) + len(primes_degrees))
    for p in primes:
        print(p, end = ' ')
    for pd in primes_degrees:
        print(pd, end = ' ')


def primes(n):
    sieve = set(range(3, n + 1, 2))
    if n >= 2:
        sieve.add(2)
    for i in range(3, int(n ** 0.5) + 1, 2):
        if i in sieve:
            sieve -= set(range(2 * i, n + 1, i))
    return sieve


n = int(input())
res = []
for i in primes(n):
    k = i
    while k <= n:
        res.append(str(k))
        k *= i

print(len(res))
print(' '.join(res))

n = int(input())
a = list(range(n+1))
a[1] = 0
lst = []

i = 2
while i <= n:
    if a[i] != 0:
        lst.append(a[i])
        for j in range(i, n+1, i):
            a[j] = 0
    i += 1

for i in range(len(lst)):
    x = lst[i]
    m = x
    while m*x <= n:
        lst.append(m*x)
        m *= x

print(len(lst))
print(" ".join(map(str, lst)))


n = int(input())
questions = []
for i in range(2, n + 1):
	if all(i % q != 0 for q in questions):
		x = i
		while x <= n:
			questions.append(x)
			x *= i
print(len(questions))
print(' '.join(str(q) for q in questions))


def Prime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0: return 0
    return 1
n=int(input())
ans=[]
for i in range(2,n+1):
    if Prime(i):
        ans+=[str(i)]
        t=i
        while t*i<=n:
            t*=i
            ans+=[str(t)]
print(len(ans))
print(' '.join(ans))

P=print
R=range
n=int(input())
x=' '.join([' '.join(str(j**i)for i in R(1,11)if j**i<=n)for j in R(2,n+1)if 0==sum(j%i==0for i in R(2,j))])
P(len(x.split()))
P(x)

n = int(input())

def prime(n):
    i = 3
    if n == 2 :
        return True
    if n % 2 == 0 :
        return False
    while i*i <= n :
        if n % i == 0 :
            return False
        i += 2
    return True

pr = [i for i in range(2,n+1) if prime(i)]
prm = []
for p in pr :
    x = p
    prm.append(x)
    while True:
        #print(x)
        x *= p
        if x > n :
            break
        prm.append(x)

print(len(prm))
print(*prm)


n = int(input())

def isprime(x):
    for i in range(2, x):
        if x%i == 0:
            return False
    else:
        return True

l = []
for i in range(2, n+1):
    if isprime(i) == True:
        l.append(i)

l2 = []
for i in l:
    c = 1
    while i**c <= n:
        l2.append(i**c)
        c += 1

print(len(l2))
for i in l2:
    print(i, end = ' ')