10392 - Factoring Large Numbers

All about problems in Volume 103. 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
minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

10392 - Factoring Large Numbers

Post by minskcity » Wed Mar 31, 2004 10:35 pm

Can anybody give me a hint on how to solve this problem?

The worst case is 32bitprime * 32bitprime, which means I have to know all primes up to 32bit long...

How can I compute them (fast)????

It I had 5Gig of memory, I would be able to do it in under 5min.. :lol: :-?

Any suggestions?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Apr 01, 2004 2:49 am

Try naive.. it's fast enough for this problem..

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Thu Apr 01, 2004 4:25 am

Larry wrote:Try naive.. it's fast enough for this problem..
You mean divide the number by two and then all odds?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Apr 01, 2004 8:42 am

You don't have to know all primes in 32bit range. It's enough to know primes in 16bit range ;-) In this range it's very easy to compute all primes ...
Thik about it :-)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Thu Apr 01, 2004 5:05 pm

Dominik Michniewski wrote:You don't have to know all primes in 32bit range. It's enough to know primes in 16bit range ;-) In this range it's very easy to compute all primes ...
Thik about it :-)

Best regards
DM
As far as I understand, if input is a 64bit prime, I have to try to divide it by all primes up to 32bit before I can be sure I was given a prime.(unless I use probabalistic prime testing)
Am I wrong?

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Thu Apr 01, 2004 7:32 pm

Use the method of sqrt to factorize the given number(The bangla method :D ).It's really easy.Try to make this code efficient by some small changes.It's really easy and simple.
cuii e

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Apr 01, 2004 8:24 pm

You have right minskcity, I misread problem description ...
But as I see in my code, it's really not necessary to compute all primes in 32bit range ... Naive algorithm is still nice for this problem :-)

I observe thatyou can use iterative algorithm : when number is prime, you should check only numbers in range 2..sqrt(number). and number is shrinking after each step, so sqrt(number) go down :-) Maybe this help you ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Fri Apr 02, 2004 12:49 am

alu_mathics wrote:Use the method of sqrt to factorize the given number(The bangla method :D ).It's really easy.Try to make this code efficient by some small changes.It's really easy and simple.
Factorizing an arbitrary 64bit number reasonably fast is not "easy and simple": my programs was accepted by judge in 0.3sec, but if I give it 1000 big primes as input it will run for 10 hours or so...
This problem reminded me another "easy" problem that asked to find a square root of 100-digits number, but the actual input did not contain numbers over 35 digits long.

JohnTortugo
New poster
Posts: 18
Joined: Sun Jul 20, 2008 7:05 pm

Re: 10392 - Factoring Large Numbers

Post by JohnTortugo » Mon Aug 11, 2008 10:59 pm

Hello there.

I'm getting W.A in this problem, can someone give me some test cases?

below is my code.

Thanks for any help.

Code: Select all

#include <iostream>
#include <math.h>

using namespace std;

int main(void) {
	
	long long int n;
	long long int sq;
	long long int i=0, c=0;

	while (cin >> n && n >= 0) {
		  if (i) cout << endl;
		  
		  c = n;
		  while((c % 2) == 0) {
		      cout << "    2" << endl;
			  c = c / 2;		   
		  }
		  
		  i = 3;
		  while (i <= (sqrt(c) + 1)) {
		  		if ((c % i) == 0) {
		      	   cout << "    " << i << endl;
		      	   c = c / i;
				}
				else {
				   i = i + 2;	 
				}
		  }
		  
		  if (c > 1) cout << "    " << c << endl;
	}
	
	return 0;	
}

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10392 - Factoring Large Numbers

Post by stcheung » Wed Jan 07, 2009 8:25 am

Instead of outputting a blank line between test cases, you should output a blank line after each test case (including the last one). On the other hand, thanks for your program. I was implementing the same "naive" idea but got TLE, which I thought was reasonable at first. Then I saw your program got WA instead of TLE and realized checking "i<=sqrt(c)+1" was actually faster than checking say "i*i<=c".

smoothdurban
New poster
Posts: 1
Joined: Thu Oct 29, 2009 8:57 pm

Re: 10392 - Factoring Large Numbers

Post by smoothdurban » Thu Nov 12, 2009 4:33 pm

I am having a formatting output issue and I can't seem to find where it is.

Anyone know?

Code: Select all

import java.io.*;


public class Main {
	public static void main(String[] args) throws IOException {

		BufferedReader vhod = new BufferedReader(new InputStreamReader(
				System.in)); 


		while (true) {

			String s = vhod.readLine();
			if (s.equals("-1")) break;


			long m = Long.parseLong(s);
			long n = 0;
			long i = 0;

			n = m;

			while(n%2 == 0)
			{
				System.out.println("    2");
				n = n/2;
			}
			i = 3;
			while (i <= (Math.sqrt(n))+1) 
			{
				if ((n % i) == 0) {
					System.out.println("    " +i);
					n = n / i;
				}
				else {
					i = i + 2;    
				}
			}
			if (n > 1)
				{
				System.out.println("    "+n);
				
				}
		}


	}

}

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10392 - Factoring Large Numbers

Post by Shafaet_du » Sun May 08, 2011 8:25 pm

I have used ordinary prime factoring algo,i generated primes upto 10^7 (though it wasnt necessary)
Try this:

Code: Select all

9999999999999999
3242345235676578
5345234788786864
4325243658766786
-1

out:

Code: Select all

    3
    3
    11
    17
    73
    101
    137
    5882353

    2
    3
    3
    3
    60043430290307

    2
    2
    2
    2
    17
    19
    31
    33364343783

    2
    7
    308945975626199


RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 10392 - Factoring Large Numbers

Post by RC's » Thu Sep 08, 2011 4:52 pm

Hi, I'm getting WA. I tried previous cases mentioned in this forum and produced same result, but I still got WA.
My algorithm is to calculate all primes less than 10^6 and try dividing the input.
Anyone can help me? Probably with some I/O cases
Thanks

EDIT : got AC already.. I missed printing "\n" after the last testcase. It was very strange, should be PE instead of WA.

torryton
New poster
Posts: 3
Joined: Thu Nov 10, 2011 12:45 pm

Re: 10392 - Factoring Large Numbers

Post by torryton » Thu Nov 10, 2011 12:50 pm

Each positive number from the input must be factored and all factors (other than 1) printed out. The factors must be printed in ascending order with 4 leading spaces preceding a left justified number, and followed by a single blank line.

alimbubt
New poster
Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm
Location: BUBT,Dhaka, Bangladesh
Contact:

Re: 10392 - Factoring Large Numbers

Post by alimbubt » Sun Apr 07, 2013 10:58 pm

Sample Input- Output:

Input:

Code: Select all

1000007
10000009
2387468238648623864
761253475173152355522
77777777777812222222222
1000000000000223657
237424528
23482397493264962346826
3245986234596236523695665
2734823482584528458248
235429469249269462946926496
3593057032750375730570
Output:

Code: Select all

    29
    34483

    23
    434783

    2
    2
    2
    641
    55331
    8414359573

    4936968151060739266

    6304763052752609166

    31
    32258064516136247

    2
    2
    2
    2
    11
    1349003

Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/

Post Reply

Return to “Volume 103 (10300-10399)”