## 10858 - Unique Factorization

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

### 10858 - Unique Factorization

Hi all,
I'm getting tle. Here is my process that i applied.
1. Generate all prime factors upto 2000000 and store them.
2. Then get the value n and iterate to find out the result, sort and print them.
My question is, is this problem solvable by easy way ?? I think i make the problem more complex. Is there any way to generate all the values in non-decreasing order ?? Any idea or sugesstion ??? Thanx in advance.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

### Re: 10858 Unique Factorization

Chok wrote:Hi all,
I'm getting tle. Here is my process that i applied.
1. Generate all prime factors upto 2000000 and store them.
2. Then get the value n and iterate to find out the result, sort and print them.
My question is, is this problem solvable by easy way ?? I think i make the problem more complex. Is there any way to generate all the values in non-decreasing order ?? Any idea or sugesstion ??? Thanx in advance.
it seems very strange, but you don't have to generate prime factors, i use simple algo, it looks like this:

void generate(int number,int lastdivisor) {
if(number==1)
print stack;
else
for all numbers p from lastdivisor to sqrt(number)
check if number%p==0 {
add to stack p
generate(number/p,p);
delete p from stack
}
}

where stack is a structure where you can store actuall divisors

ofcourse it is not a full algo, but only idea [fast - acc in 0.072 in pascal]

hope it helps, if i wrote something wrong please correct me

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
I get too many WR.
plz simple IO.

Thanks
Keep posting

sapnil

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10858 - Unique Factorization

Input:

Code: Select all

``````24
0
``````
AC output:

Code: Select all

``````6
2 2 2 3
2 2 6
2 3 4
2 12
3 8
4 6
``````
Check input and AC output for thousands of problems on uDebug!