## TLE '17 Contest 5 P3 - Willson and Factorization

View as PDF

Points: 7 (partial)
Time limit: 2.0s
PyPy 2 3.0s
PyPy 3 3.0s
Python 2 4.0s
Python 3 4.0s
Memory limit: 256M

Author:
Problem types
Willson is sad because nobody likes him.

Willson the Canada Goose is like any other Canada Goose - he suspects that many humans don't like him.

As a result, he challenges you to do the following problem:

Consider the set .

We say that an element in is a unit if there is some element in with .

We say that a non-zero, non-unit element in is irreducible if there are no elements in where are not units and .

We say that a non-zero, non-unit element in is prime if for all elements in , if for some element in , then for some element in or for some element in .

Given , please output all of the units, irreducibles, and primes of .

#### Input Specification

The only line of input will contain a single integer, .

For of the points, is prime.

For an additional of the points, .

For an additional of the points, .

#### Output Specification

Output, in numerical order, first the units, then the irreducibles, then the primes of . See the Sample Output for more specific formatting.

#### Sample Input 1

10

#### Sample Output 1

Units:
1
3
7
9
Irreducibles:
Primes:
2
4
5
6
8

#### Sample Input 2

12

#### Sample Output 2

Units:
1
5
7
11
Irreducibles:
2
10
Primes:
2
3
9
10