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

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

10858 - Unique Factorization

Post by Chok » Fri Jul 29, 2005 1:49 pm

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

Post by Monsoon » Fri Jul 29, 2005 3:16 pm

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 :D

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Fri Aug 31, 2007 9:10 pm

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

Post by brianfry713 » Mon Jul 08, 2013 10:44 am

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!

Post Reply

Return to “Volume 108 (10800-10899)”