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 "nonrectangular." 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 nonrectangular.
After playing for some time, the king started to notice that every integer greater than 1 could be written as a product of nonrectangular 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 10^{7} 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 nonrectangular numbers, following the example of the sample output. Factors must be written in nondecreasing 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:
20180102 13:18:01
Assume n <= 10004569 rather than 10^7. Fin annoying waste of time debugging when it's the problem statement that is wrong. 

kr_chandan15:
20160824 22:41:14
how to remove the last printed *


mkfeuhrer:
20160815 17:26:54
most no. of mistakes ever done :(.... use sieve simply(slight optimization) ....10^7 size array (costed me lot of WA)!!


minhthai:
20160320 06:34:52
please don't comment spoiler :( 

dragonemperor:
20151019 19:08:51
Easy problem. With ********************** spoil removed by Francky ******** Last edit: 20160320 11:34:19 

parbays:
20140120 16:11:50
Indeed, removing one redundant division per while loop count moved the sol from TLE to AC. 

jehovah:
20131223 17:54:01
little trick to get AC in time less than 0.5s 

Martijn Muijsers:
20131127 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:
20130125 14:41:30
i get WA !!!


Snehasish Roy ;):
20120814 16:01:37
Very Nice Question.

Added by:  Miorel Palii 
Date:  20091028 
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 