Page 1 of 1

10392 - Factoring Large Numbers

Posted: Wed Mar 31, 2004 10:35 pm
by minskcity
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?

Posted: Thu Apr 01, 2004 2:49 am
by Larry
Try naive.. it's fast enough for this problem..

Posted: Thu Apr 01, 2004 4:25 am
by minskcity
Larry wrote:Try naive.. it's fast enough for this problem..
You mean divide the number by two and then all odds?

Posted: Thu Apr 01, 2004 8:42 am
by Dominik Michniewski
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

Posted: Thu Apr 01, 2004 5:05 pm
by minskcity
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?

Posted: Thu Apr 01, 2004 7:32 pm
by alu_mathics
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.

Posted: Thu Apr 01, 2004 8:24 pm
by Dominik Michniewski
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

Posted: Fri Apr 02, 2004 12:49 am
by minskcity
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.

Re: 10392 - Factoring Large Numbers

Posted: Mon Aug 11, 2008 10:59 pm
by JohnTortugo
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;	
}

Re: 10392 - Factoring Large Numbers

Posted: Wed Jan 07, 2009 8:25 am
by stcheung
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".

Re: 10392 - Factoring Large Numbers

Posted: Thu Nov 12, 2009 4:33 pm
by smoothdurban
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);
				
				}
		}


	}

}

Re: 10392 - Factoring Large Numbers

Posted: Sun May 08, 2011 8:25 pm
by Shafaet_du
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


Re: 10392 - Factoring Large Numbers

Posted: Thu Sep 08, 2011 4:52 pm
by RC's
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.

Re: 10392 - Factoring Large Numbers

Posted: Thu Nov 10, 2011 12:50 pm
by torryton
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.

Re: 10392 - Factoring Large Numbers

Posted: Sun Apr 07, 2013 10:58 pm
by alimbubt
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