TUTMRBL - Playing with Marbles


Playing with marbles is one of the king's favorite pastimes. He especially enjoys a game which was taught to him by Eratosthenes, a visiting mathematician from Greece. The rules are very complicated but it all boils down to arranging marbles in a (filled) rectangular shape to score points. If playing with 24 marbles, for example, King Tut could make a 4 by 6 rectangle, or a 3 by 8 rectangle, or a 2 by 12 rectangle. Even the boring 1 by 24 rectangle is allowed. Other numbers of marbles, however, such as 23, make things difficult for the king. Try as he might, the only rectangle he can make is 1 by 23. (Note that rectangles are equivalent under rotation, so a 23 by 1 rectangle would not be a new shape.)

King Tut has decided to call numbers n which can form only the unexciting 1 by n rectangle "non-rectangular." Conversely, numbers like 24, which allow for the formation of more than one rectangle, shall henceforth be referred to as "rectangular." Playing with a single marble is not very interesting at all, so the number 1 will by definition considered neither rectangular nor non-rectangular.

After playing for some time, the king started to notice that every integer greater than 1 could be written as a product of non-rectangular numbers. Were he a mathematician, he would try to prove this claim (which, incidentally, is true). However, the king is more of the engineer type, so he's going to make you verify the claim using brute force! While you're at it, also tell the king how many rectangles can be constructed given a certain number of marbles.

Input

There will be several test cases, one per line, each consisting of a single integer between 2 and 107 inclusive. An input of zero will be used to tell your program to stop processing.

Output

For each test case, print out two lines! The first should show the given number of marbles written as a product of non-rectangular numbers, following the example of the sample output. Factors must be written in non-decreasing order and separated by multiplication signs. Also print out spaces around the equals and multiplication signs to improve readability. The second line of output for each test case should be in the format: "With X marbles, Y different rectangles can be constructed." Again, don't forget to replace X and Y with the proper values.

Example

Input:
24
23
0

Output:
24 = 2 * 2 * 2 * 3
With 24 marbles, 4 different rectangles can be constructed.
23 = 23
With 23 marbles, 1 different rectangles can be constructed.

hide comments
nadstratosfer: 2018-01-02 13:18:01

Assume n <= 10004569 rather than 10^7. F-in annoying waste of time debugging when it's the problem statement that is wrong.

kr_chandan15: 2016-08-24 22:41:14

how to remove the last printed *

mkfeuhrer: 2016-08-15 17:26:54

most no. of mistakes ever done :-(.... use sieve simply(slight optimization) ....10^7 size array (costed me lot of WA)!!
take care of printing!(in ascending order)

minhthai: 2016-03-20 06:34:52

please don't comment spoiler :(

dragonemperor: 2015-10-19 19:08:51

Easy problem. With ********************** spoil removed by Francky ********

Last edit: 2016-03-20 11:34:19
parbays: 2014-01-20 16:11:50

Indeed, removing one redundant division per while loop count moved the sol from TLE to AC.

jehovah: 2013-12-23 17:54:01

little trick to get AC in time less than 0.5s

Martijn Muijsers: 2013-11-27 13:39:12

I didn't talk to Eratosthenes if you know what I mean :P great problem, the problem statement is so predictable XD

moustafa maher: 2013-01-25 14:41:30

i get WA !!!

Snehasish Roy ;): 2012-08-14 16:01:37

Very Nice Question.
Learnt a lot from it :)


Added by:Miorel Palii
Date:2009-10-28
Time limit:1.943s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C++ 4.3.2 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:University of Florida Local Contest - September 9, 2007