Strange order
Given an integer $$n$$. Initially you have permutation $$p$$ of size $$n$$: $$p_i = i$$. To build new array $$a$$ from $$p$$ following steps are done while permutation $$p$$ is not empty:
- Choose maximum existing element in $$p$$ and define it as $$x$$;
- Choose all such $$y$$ in $$p$$ that $$\gcd(x, y) \neq 1$$;
- Add all chosen numbers into array $$a$$ in decreasing order and remove them from permutation.
Your task is to find $$a$$ after $$p$$ became empty.
Note: $$\gcd(a, b)$$ is the greatest common divisor of integers $$a$$ and $$b$$.
Input format
Input contains single integer $$n$$ ($$1 \leq n \leq 2 \cdot 10^6$$) — the size of permutation $$p$$.
Output format
Print $$n$$ integers — array $$a$$.
Explanation
It's needed $$4$$ iterations to create array $$a$$:
- Add $$5$$
- Add $$4$$ and $$2$$
- Add $$3$$
- Add $$1$$
Time Limit:
2.0 sec(s)
for each input file.
Memory Limit:
512 MB
Source Limit:
1024 KB
Marking Scheme:
Marks are awarded when all the testcases pass.
Allowed Languages:
C,
C++,
C++14,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Julia,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic,
Kotlin