Kate has a set $S$ of $n$ integers $\{1, \dots, n\} $. 

She thinks that imperfection of a subset $M \subseteq S$ is equal to the maximum of $gcd(a, b)$ over all pairs $(a, b)$ such that both $a$ and $b$ are in $M$ and $a \neq b$. 

Kate is a very neat girl and for each $k \in \{2, \dots, n\}$ she wants to find a subset that has the smallest imperfection among all subsets in $S$ of size $k$. There can be more than one subset with the smallest imperfection and the same size, but you don't need to worry about it. Kate wants to find all the subsets herself, but she needs your help to find the smallest possible imperfection for each size $k$, will name it $I_k$. 

Please, help Kate to find $I_2$, $I_3$, ..., $I_n$.


-----Input-----

The first and only line in the input consists of only one integer $n$ ($2\le n \le 5 \cdot 10^5$)  — the size of the given set $S$.


-----Output-----

Output contains only one line that includes $n - 1$ integers: $I_2$, $I_3$, ..., $I_n$.


-----Examples-----
Input
2

Output
1 
Input
3

Output
1 1 


-----Note-----

First sample: answer is 1, because $gcd(1, 2) = 1$.

Second sample: there are subsets of $S$ with sizes $2, 3$ with imperfection equal to 1. For example, $\{2,3\}$ and $\{1, 2, 3\}$.

Source: codeforces | Difficulty: HARD
Tags: Sorting

Amortized analysis

Implementation

Greedy algorithms

Number theory

Mathematics


Solutions:
N = int(input())
primes = [0] * (N + 1)
for i in range(2, N + 1):
	if primes[i] == 0:
		primes[i] = 1
		for j in range(i * 2, N + 1, i):
			primes[j] = -1
primes = [i for (i, p) in enumerate(primes) if p == 1]
res = [0] * (N + 1)
for p in primes:
	res[p] = 1
for p in primes:
	for j in range(p * 2, N + 1, p):
		if res[j] == 0:
			res[j] = max(p, j // p)
print(' '.join(map(str, sorted(res[2:]))))


n = int(input())
arr = [1] * (n + 1)
p = 2
while p * p <= n:
	if arr[p] == 1:
		for i in range(p * 2, n + 1, p):
			arr[i] = max(arr[i], p, i // p)
	p += 1
arr.sort()
print(' '.join([str(x) for x in arr[2:]]))


n = int(input())
res = [1] * (n + 1)
for i in range(2, n + 1):
	j = i
	while i * j <= n:
		res[i * j] = max(res[i * j], j)
		j += 1
res.sort()
print(' '.join(map(str, res[2:])))


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List
N = int(input())
maxdiv = [0 for _ in range(N + 1)]
maxdiv[1] = 1
for i in range(2, N + 1):
	if maxdiv[i]:
		continue
	v = i
	d = 1
	while v <= N:
		if maxdiv[v] == 0:
			maxdiv[v] = d
		v += i
		d += 1
maxdiv = maxdiv[1:]
maxdiv.sort()
ans = []
maxd = 0
for v in maxdiv:
	maxd = max(maxd, v)
	ans.append(maxd)
print(' '.join(map(str, ans[1:])))


import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

def input():
	return sys.stdin.readline()

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())
spf = [0] * 500005

def sieve():
	spf[1] = 1
	for i in range(2, 500005):
		spf[i] = i
	for i in range(4, 500005, 2):
		spf[i] = 2
	for i in range(3, int(500005 ** 0.5) + 1):
		if spf[i] == i:
			for j in range(i * i, 500005, i):
				if spf[j] == j:
					spf[j] = i
sieve()
n = int(input())
res = []
for i in range(2, n + 1):
	res.append(i // spf[i])
res.sort()
print(*res)


n = int(input())
i = 2
s = [1] * (n + 1)
(s[0], s[1]) = (0, 0)
m = n / 2 + 1
while i <= m:
	j = 2
	while j * i <= n:
		s[i * j] = i
		j += 1
	i += 1
s.sort()
for i in s[2:]:
	print(i, end=' ')


n = int(input())
arr = [0] * (n + 1)
for i in range(1, n + 1):
	for j in range(i + i, n + 1, i):
		arr[j] = i
arr.sort()
for i in range(2, n + 1):
	print(arr[i], end=' ')


n = int(input())
cur = n
ans = [0] * (n + 1)
used = [0] * (n + 1)
for j in range(n // 2, 1, -1):
	for x in range(2 * j, n + 1, j):
		if used[x] == 0:
			used[x] = 1
			ans[cur] = j
			cur -= 1
for x in range(1, cur + 1):
	ans[x] = 1
print(' '.join([str(x) for x in ans[2:]]))


from collections import *
from math import *
N = int(500000.0 + 5)
p = [0 for i in range(N)]
for i in range(2, N):
	if p[i] == 0:
		for j in range(i * i, N, i):
			if p[j] == 0:
				p[j] = i
n = int(input())
a = [1 for i in range(n + 1)]
primes = []
ct = 0
for i in range(1, n + 1):
	if p[i] == 0:
		ct += 1
		primes.append(i)
g = 2
dig = 2 * g
lim = g * g
j = 2
m = ct
for i in range(ct + 1, n + 1):
	if dig > lim or dig > n:
		g += 1
		dig = 2 * g
		j = 2
		if p[g] == 0:
			lim = g * g
		else:
			lim = p[g] * g
	a[i] = g
	dig = g * primes[j]
	j += 1
for i in range(2, n + 1):
	print(a[i], end=' ')
print()


n = int(input())
a = [0] * n
d = [0] * n
for i in range(1, n + 1):
	for j in range(i + i, n + 1, i):
		d[j - 1] = i
	a[i - 1] = d[i - 1]
a = sorted(a)[1:]
for x in a:
	print(x)


def main():
	import sys
	from heapq import heappop, heappush
	input = sys.stdin.readline
	N = int(input())
	pq = []
	seen = [0] * (N + 1)
	for i in range(N // 2, 1, -1):
		for j in range(2, N):
			ii = i * j
			if ii > N:
				break
			if not seen[ii]:
				seen[ii] = 1
				heappush(pq, -i)
	ans = [1] * (N - 1)
	i = -1
	while pq:
		ans[i] = -heappop(pq)
		i -= 1
	print(*ans)
main()


n = int(input())
ans = [1] * (n + 1)
for i in range(2, n + 1):
	j = i
	while j * i <= n:
		ans[j * i] = max(ans[j * i], j)
		j += 1
a = sorted(ans)
print(*a[2:])


def get_primes(n):
	res = [2]
	arr = [True] * ((n - 1) // 2)
	i = 0
	for i in range(len(arr)):
		if arr[i]:
			a = i * 2 + 3
			res.append(a)
			for ii in range(i + a, len(arr), a):
				arr[ii] = False
	return res
n = int(input())
primes = get_primes(n)
res = ['1'] * min(n - 1, len(primes))
left = n - 1 - len(res)
ii = 2
while left > 0:
	for a in primes:
		if ii * a <= n:
			res.append(str(ii))
			left -= 1
		else:
			break
		if ii % a == 0 or left == 0:
			break
	ii += 1
print(' '.join(res))


n = int(input())
ans = [0 for i in range(n + 1)]
for i in range(1, n + 1):
	for j in range(2 * i, n + 1, i):
		ans[j] = i
ans.sort()
print(*ans[2:])


def solve(n):
	nums = [1] * (n + 1)
	p = 2
	while p * p <= n:
		if nums[p] == 1:
			for i in range(p * 2, n + 1, p):
				nums[i] = max(nums[i], p, i // p)
		p += 1
	return sorted(sorted(nums[2:]))
n = int(input())
print(' '.join([str(x) for x in solve(n)]))


def f(n):
	d = [1] * (n + 1)
	for i in range(2, int(n ** 0.5) + 1):
		if d[i] > 1:
			continue
		for j in range(2 * i, n + 1, i):
			d[j] = max(d[j], j // i)
	return d
n = int(input())
d = f(n)[1:]
d.sort()
print(*d[1:])


n = int(input()) - 1
p = [1] * n
for i in range(n):
	for j in range(2 * i + 2, n, i + 2):
		p[j] = i + 2
print(*sorted(p))


n = int(input())
A = [1 for i in range(n + 1)]
for i in range(2, n):
	j = 2 * i
	while j <= n:
		A[j] = i
		j += i
ans = sorted(A)
ans = ans[2:]
print(*ans)


from sys import stdin, stdout
input = stdin.readline
print = stdout.write
R = lambda : list(map(int, input().split()))
n = int(input())
s = [0] * (n + 1)
vis = [0] * (n + 1)
u = 2
while u * u <= n:
	if not vis[u]:
		for i in range(u * 2, n + 1, u):
			if vis[i]:
				continue
			vis[i] = 1
			s[i // u] += 1
	u += 1
for i in range(2, n + 1):
	if not vis[i]:
		s[1] += 1
res = []
for i in range(n + 1):
	for j in range(s[i]):
		res.append(i)
print(' '.join(map(str, res)) + '\n')


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	n = int(input())
	arr = [1] * (n + 1)
	for i in range(2, n // 2 + 1):
		for j in range(i + i, n + 1, i):
			arr[j] = i
	arr.sort()
	print(' '.join([str(x) for x in arr[2:]]))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def main():
	for _ in inputt(1):
		(n,) = inputi()
		S = [1] * (n + 1)
		for i in range(2, n // 2 + 1):
			for j in range(i * 2, n + 1, i):
				S[j] = i
		S.sort()
		print(*S[2:])
import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	for x in args:
		file.write(str(x))
	file.write(kwargs.pop('end', '\n'))
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inputt = lambda t=0: range(t) if t else range(int(input()))
inputi = lambda : map(int, input().split())
inputl = lambda : list(inputi())
from math import *
from heapq import *
from bisect import *
from itertools import *
from functools import reduce, lru_cache
from collections import Counter, defaultdict
import re, copy, operator, cmath
from builtins import *
main()


n = int(input())
exist = [True] * (n + 1)
ans = []
for now in range(n // 2, 0, -1):
	for i in range(now * 2, n + 1, now):
		if exist[i]:
			ans.append(now)
			exist[i] = False
ans.reverse()
print(*ans)


from sys import stdin, stdout
n = int(stdin.readline())
s_a = [1 for _ in range(n + 1)]
for i in range(2, n):
	for j in range(i * 2, n + 1, i):
		s_a[j] = i
s_a.sort()
s_a.pop(0)
s_a.pop(0)
stdout.write(' '.join(map(str, s_a)))


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	lim = n + 1
	sieve = [1] * lim
	for i in range(2, lim):
		for x in range(2 * i, lim, i):
			sieve[x] = i
	cou = [0] * lim
	for i in sieve[2:]:
		cou[i] += 1
	ans = []
	for (ind, i) in enumerate(cou):
		ans.extend([ind] * min(i, n - len(ans) - 1))
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	n = int(input())
	imp = n // 2
	ans = [1] * (n + 1)
	used = [False] * (n + 1)
	cur = n
	while imp > 1:
		first = False
		for i in range(imp, n + 1, imp):
			if not used[i]:
				if not first:
					first = True
				else:
					used[i] = True
					ans[cur] = imp
					cur -= 1
		imp -= 1
	print(*ans[2:])


from collections import Counter
from sys import stdin, stdout

def write(_s):
	stdout.write(_s)

def writeint(_s):
	stdout.write(str(_s))

def writelist(_l):
	stdout.write(''.join(_l))

def read():
	return stdin.readline().split(' ')

def readint():
	return int(stdin.readline())

def readints():
	return map(int, stdin.readline().split(' '))
n = readint()
divs = [0] * (n + 1)
for i in range(2, n + 1):
	j = i
	while j <= n:
		if divs[j] == 0:
			divs[j] = j // i
		j += i
divs[1] = 1
counter = Counter(divs)
counter[1] -= 1
c = 0
for divisor in range(1, n + 1):
	for _ in range(counter[divisor]):
		if c <= n - 2:
			writeint(divisor)
		else:
			break
		write(' ')


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
n = val()
s = set([*range(1, n + 1)])
sieve = [True] * (n + 1)
l = [1]
for i in range(2, n + 1):
	if sieve[i]:
		l.append(i)
		for j in range(2 * i, n + 1, i):
			sieve[j] = False
he = []
ans = [1] * len(l)
indic = {}
for i in l:
	indic[i] = 1
curr = [2] * (len(l) + 1)
p = [1] * len(l)
l = l[1:]
for i in l:
	curr = 2
	while i * curr <= n:
		if curr * i not in indic:
			ans.append(max(i, curr))
			indic[curr * i] = 1
		curr += 1
ans.sort()
print(*ans[1:])


import sys, math, cmath, time
start_time = time.time()

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())

def solve():
	n = inp()
	q = [1] * math.ceil(n / 2)
	qw = len(q)
	w = [1] * (n + 1)
	for i in range(n):
		j = 2 * (i + 1)
		while j <= n:
			qw = 1
			w[j] = i + 1
			j = j + i + 1
	w.sort()
	print(*w[qw + 1:])
ONLINE_JUDGE = __debug__
if not ONLINE_JUDGE:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = sys.stdin.readline
t = 1
for tt in range(t):
	solve()
if not ONLINE_JUDGE:
	print('Time Elapsed:', time.time() - start_time, 'seconds')
sys.stdout.close()


n = int(input())
x = [0, 1] + [0] * (n - 1)
for i in range(2, n + 1):
	if x[i]:
		continue
	for j in range(i, n + 1, i):
		if x[j]:
			continue
		x[j] = j // i
print(*sorted(x[2:]))


n = int(input())
div = [0] * (n + 5)

def sieve():
	for i in range(2, n + 1):
		if div[i] != 0:
			continue
		for j in range(i, n + 1, i):
			if div[j] == 0:
				div[j] = i
	return
a = []
sieve()
b = []
for i in range(2, n + 1):
	if div[i] == i:
		b.append(i)
		a.append(1)
for i in range(2, n + 1):
	if i > n // 2:
		break
	for k in b:
		if i * k > n:
			break
		if div[i] == i:
			if k > i:
				break
			a.append(i)
		else:
			y = div[i * k]
			if i * k / y > i:
				break
			a.append(i)
print(*a)


import random
from math import ceil, sqrt, gcd, floor

def solve_1(n):
	smallest = []
	for i in range(2, n + 1):
		min_imp = [999999999999999999999] * 1
		combination(n, [0] * i, 0, 1, min_imp, [0] * n)
		smallest.append(min_imp[0])
	return smallest

def combination(n, c, pos, l, min_imp, mark):
	if pos == len(c):
		imperfection = 1
		for i in range(len(c)):
			for j in range(len(c)):
				if c[i] != c[j]:
					imperfection = max(imperfection, gcd(c[i], c[j]))
		min_imp[0] = min(imperfection, min_imp[0])
		return
	for i in range(l, n + 1):
		if mark[i - 1] != 1:
			c[pos] = i
			mark[i - 1] = 1
			combination(n, c, pos + 1, c[pos] + 1, min_imp, mark)
			mark[i - 1] = 0
	return

def solve_2(n):
	gd = [0] * (n - 1)
	for i in range(2, n + 1):
		gd[i - 2] = greatest_divisor_2(i)
	merge_sort(gd, 0, len(gd) - 1, [0] * len(gd))
	return gd

def greatest_divisor_1(n):
	d = 1
	for i in range(1, ceil(n / 2) + 1):
		if n % i == 0:
			d = i
	return d

def greatest_divisor_2(n):
	d = 1
	for i in range(2, int(sqrt(n) + 1)):
		if n % i == 0:
			d = n // i
			break
	return d

def merge_sort(A, l, r, B):
	if l < r:
		m = (r + l) // 2
		merge_sort(A, l, m, B)
		merge_sort(A, m + 1, r, B)
		merge(A, l, r, B)
	return

def merge(A, l, r, B):
	m = (r + l) // 2
	(k, p, q) = (l, l, m + 1)
	while p <= m and q <= r:
		if A[p] < A[q]:
			B[k] = A[p]
			p += 1
		else:
			B[k] = A[q]
			q += 1
		k += 1
	while p <= m:
		B[k] = A[p]
		k += 1
		p += 1
	while q <= r:
		B[k] = A[q]
		k += 1
		q += 1
	for i in range(l, r + 1):
		A[i] = B[i]
	return

def solve_3(n):
	gd = sieve(n)
	merge_sort(gd, 0, len(gd) - 1, [0] * len(gd))
	return gd

def sieve(n):
	gd = [1] * (n - 1)
	sieve = [False] * (n - 1)
	for i in range(2, floor(sqrt(n)) + 1):
		if not sieve[i - 2]:
			for j in range(i, n // i + 1):
				sieve[i * j - 2] = True
				gd[i * j - 2] = max(gd[i * j - 2], i, j)
	return gd

def main():
	n = int(input())
	print(' '.join((str(i) for i in solve_3(n))))
	return

def random_cases():
	n = random.randint(2, 100)
	print('Case: \n' + 'n = ' + str(n))
	print(' '.join((str(i) for i in solve_3(n))))
	return

def tester():
	for i in range(1, 20):
		n = random.randint(2, 10000)
		s1 = solve_1(n)
		s2 = solve_2(n)
		s3 = solve_3(n)
		print('Case ' + str(i) + ':\n' + 'n = ' + str(n))
		print('solucion fuerza bruta : ' + ' '.join((str(i) for i in s1)))
		print('solucion eficiente : ' + ' '.join((str(i) for i in s2)))
		print('solucion con criba : ' + ' '.join((str(i) for i in s3)))
		for i in range(min(len(s1), len(s2), len(s3))):
			if (s1[i] != s2[i] or s2[i] != s3[i]) or (len(s1) != len(s2) or len(s2) != len(s3)):
				print('Wrong Answer\n')
				return
		print('Accepted\n')
	return
main()


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
mod = int(1000000000.0 + 7)
MAX_SIZE = 1000001
isprime = [True] * MAX_SIZE
prime = []
SPF = [None] * MAX_SIZE

def manipulated_seive(N):
	isprime[0] = isprime[1] = False
	for i in range(2, N):
		if isprime[i] == True:
			prime.append(i)
			SPF[i] = i
		j = 0
		while j < len(prime) and i * prime[j] < N and (prime[j] <= SPF[i]):
			isprime[i * prime[j]] = False
			SPF[i * prime[j]] = prime[j]
			j += 1
n = int(data())
manipulated_seive(n + 1)
l = [1] * len(prime)
t = 2
i = len(prime)
for i in range(2, n + 1):
	if isprime[i] == False:
		for j in prime:
			if i % j == 0:
				l.append(i // j)
				break
print(*sorted(l))


import sys
input = sys.stdin.readline
n = int(input())
arr = [1] * (n + 1)
for i in range(2, n + 1):
	j = i
	while j * i <= n:
		arr[i * j] = max(arr[i * j], j)
		j += 1
ans = sorted(arr)
print(*ans[2:])


n = int(input())
fac = [10 ** 6 for _ in range(n + 1)]
fac[1] = 1
for i in range(2, n + 1):
	if fac[i] == 10 ** 6:
		for j in range(i, n + 1, i):
			fac[j] = min(fac[j], i)
ans = sorted([i // fac[i] for i in range(1, n + 1)])
print(*ans[1:])


n = int(input())
out = [1] * (n + 1)
for i in range(2, n):
	for j in range(2 * i, n + 1, i):
		out[j] = i
print(' '.join(map(str, sorted(out[2:]))))


n = int(input())
l = []
for i in range(n + 1):
	l.append(0)
for i in range(2, n + 1):
	for j in range(i * 2, n + 1, i):
		l[j] = i
l.sort()
for i in range(2, n + 1):
	if l[i] == 0:
		print(1, end=' ')
	else:
		print(l[i], end=' ')


n = int(input())
min_div = [i for i in range(n + 1)]
for i in range(2, n + 1):
	if i * i > n:
		break
	for j in range(2 * i, n + 1, i):
		if min_div[j] == j:
			min_div[j] = i
cost = [i // min_div[i] for i in range(1, n + 1)]
cost.sort()
for c in cost[1:]:
	print(c, end=' ')
print()


def lf(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return x // i
		i += 1
	return 1
n = int(input())
d = []
for i in range(2, n + 1):
	d.append(lf(i))
d.sort()
print(' '.join(map(str, d)))


n = int(input())
L = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
	for j in range(i + i, n + 1, i):
		L[j] = i
L.sort()
print(*L[2:])


n = int(input())
v = [False for i in range(n + 1)]
ans = []
for i in range(2, n + 1):
	if not v[i]:
		ans.append(1)
		for j in range(i * 2, n + 1, i):
			if v[j]:
				continue
			ans.append(j // i)
			v[j] = True
ans = sorted(ans)
print(' '.join([str(i) for i in ans]))


n = int(input())
sieve = [-1] * (n + 1)
primes = []
for i in range(2, n + 1):
	if sieve[i] == -1:
		sieve[i] = i
		primes.append(i)
		for x in range(2 * i, n + 1, i):
			if sieve[x] == -1:
				sieve[x] = i
answer = [1] * len(primes)
c = set(primes)
c.add(1)
toAdd = 2
while len(c) != n:
	for k in primes:
		if k > sieve[toAdd]:
			break
		y = toAdd * k
		if y > n:
			break
		if y not in c:
			c.add(y)
			answer.append(toAdd)
	toAdd += 1
print(*answer)