Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Gaussian Prime Factors
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 1341Accepted: 440

Description

Let a, b, c, d be integers. The complex number a+bj, where j2 = -1, is a factor of c+dj, if there exist integers e and f such that

c + dj = (a + bj)(e + fj).

A complex number a + bj where a and b are integers is a Gaussian prime if the factors are 1, -1, -a - bj and a + bj only.

The following are Gaussian primes: 1 + j, 1 - j, 1 + 2j, 1 - 2j, 3 and 7.

The Gaussian prime factors of 5 are:

1 + 2j and 1 - 2j, or
2 + j and 2 - j, or
-1 - 2j and -1 + 2j, or
-2 - j and -2 + j.

Write a program that finds all the Gaussian prime factors of a positive integer.

Input

One line of input per case. The line represents a positive integer n.

Output

One line of output per test case. The line represents the Gaussian prime factors of n. If a + bj is a Gaussian prime factor of n, then a > 0, |b| ≥ a, if b ≠ 0. If b = 0, the output must be a.

Sample Input

2
5
6
700

Sample Output

Case #1: 1+j, 1-j 
Case #2: 1+2j, 1-2j 
Case #3: 1+j, 1-j, 3 
Case #4: 1+j, 1-j, 1+2j, 1-2j, 7

Hint

Output the Gaussian prime factors in ascending order of a. If there are more than one factors with the same a, output them in ascending order of b by absolute value. If two conjugate factors coexist, the one with a positive imaginary part precedes that with a negative imaginary part.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator