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)
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?
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.
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)
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.
#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;
}
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".
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);
}
}
}
}
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.
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.