All Tracks Math Number Theory Problem

Strange order
Tag(s):

Easy-Medium, Math

Problem
Editorial
Analytics

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:

  1. Choose maximum existing element in $$p$$ and define it as $$x$$;
  2. Choose all such $$y$$ in $$p$$ that $$\gcd(x, y) \neq 1$$;
  3. 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$$.

SAMPLE INPUT
5
SAMPLE OUTPUT
5 4 2 3 1
Explanation

It's needed $$4$$ iterations to create array $$a$$:

  1. Add $$5$$
  2. Add $$4$$ and $$2$$
  3. Add $$3$$
  4. 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, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications