oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

primesort Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

primesort.html

Problem Description

During your lunch breaks, Rar the Cat was thinking about how to set problems to test you guys on primes. He then decided to combine sorting and prime together.

Each number above 1 can be uniquely prime factorized. Eg: 12 = 2 * 2 * 3, 15 = 3 * 5. As such, given a list of N numbers, where each number is greater than 1 and not more than 1000000, your task is to sort it based on their prime factorization.

Refer to Sample Testcases for further elaboration and inference.

Input

The first line of input consist of 1 integer, N. N lines will follow with one integer each, these N lines are the list of N numbers you have to sort based on their prime factorization.

Output

Output the sorted list of N numbers, 1 number per line.

Subtasks

Subtask 1 (7%): N = 10.

Subtask 2 (24%): N = 3000.

Subtask 3 (26%): N = 50000.

Subtask 4 (43%): N = 1000000. (Memory Limit Reduced)

Subtask 5 (0%): Sample

Sample Testcase 1

Input:

5
2 3 4 5 6

Output:

2
4
6
3
5

Explanation:

2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
The numbers are differeniated by the first (lowest) prime factor first, and then followed by the second prime factor if both numbers have second prime factors. If not, the smaller number should be sorted first.

Tags

Primes, Sorting, Depth First Search

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
17202s64MBMinimum
224202s64MBMinimum
326202s64MBMinimum
443202s32MBMinimum
5012s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o primesort -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.