import math

def check(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return x > 1

def cp(n):
    k = int(math.sqrt(n))
    return k * k == n

n = int(input())
d = 0
d1 = 0

for i in range(1, n + 1):
    if cp(i):
        d += 1
    if check(i):
        d1 += 1

print(f"Co {d + 1} so chinh phuong: 0 ", end="")
for i in range(1, n + 1):
    if cp(i):
        print(i, end=" ")
print()

print(f"Co {d1} so nguyen to: ", end="")
for i in range(1, n + 1):
    if check(i):
        print(i, end=" ")

import math

def snt(x):
    if x < 2:
        return False
    if x < 4:
        return True
    if x % 2 == 0 or x % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(x)) + 1, 6):
        if x % i == 0 or x % (i + 2) == 0:
            return False
    return True

def cpp(n):
    if n < 0:
        return False
    s = int(math.sqrt(n))
    return s * s == n

n = int(input())
nt = []
cp1 = []
dem = 0
cp = 0

for i in range(n+1):
    k = int(math.sqrt(i))
    if snt(i):
        nt.append(i)
        dem += 1
    if cpp(i):
        cp1.append(i)
        cp += 1

print("Co", cp, "so chinh phuong:", " ".join(map(str, cp1)))
print("Co", dem, "so nguyen to:", " ".join(map(str, nt)))