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
-
minskcity
- Experienced poster
- Posts: 199
- Joined: Tue May 14, 2002 10:23 am
- Location: Vancouver
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..
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?
-
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

).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

).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
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:
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
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:
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
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
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:
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