Page 9 of 12
Re: 583 - Prime Factors
Posted: Sat Jan 10, 2009 4:49 pm
by fahmi
can any1 help me plz??? this is the code with seive & array,but having RTE
Code: Select all
#include<stdio.h>
#include<math.h>
long long prime[3550],flag[10000],c=0,a[100000000];
void seive(int n)
{
long long k,i,j,r;
k=sqrt(n);
for(i=1;i<=n;i++)
flag[i]=0;
flag[1]=1;
prime[0]=2;
c=1;
for(i=4;i<=n;i+=2)
flag[i]=1;
for(i=3;i<=n;i+=2)
{
if(flag[i]==0)
{
prime[c++]=i;
if(k>=i)
{
r=i+i;
for(j=i*i;j<=n;j+=r)
flag[j]=1;
}
}
}
}
int main()
{
long long n,i,j,x;
while(scanf("%lld",&n)==1)
{
if(n==0)
break;
else if(n==1)
{
printf("1 =\n");
continue;
}
x=n;
i=0;
if(n<0)
{
a[i]=-1;
i++;
n=n*(-1);
}
seive(n);
for(j=0;j<c;)
{
if(n%prime[j]==0)
{
a[i++]=prime[j];
n=n/prime[j];
}
else j++;
}
printf("%lld = %lld",x,a[0]);
for(j=1;j<i;j++)
printf(" x %lld",a[j]);
printf("\n");
}
}
Re: 583 - Prime Factors
Posted: Sat Jan 10, 2009 4:51 pm
by fahmi
& this is my code without using Array,but getting TLE.i cant fix whats d wrong with my code.plzzzz help
Code: Select all
#include<stdio.h>
int main()
{
long long n,i,j,f;
while(scanf("%lld",&n)==1)
{
if(n==0)
break;
else if(n==1)
{
printf("1 =\n");
continue;
}
f=0;
printf("%lld =",n);
if(n<0)
{
printf(" -1");
f=1;
n=n*(-1);
}
while(n%2==0)
{
if(f==0)
printf(" 2");
if(f==1)
printf(" x 2");
n=n/2;
f=1;
}
for(i=3;n>1;)
{
if(n%i==0)
{
if(f==0)
printf(" %lld",i);
else printf(" x %lld",i);
n=n/i;
f=1;
}
else i+=2;
}
printf("\n");
}
return 0;
}
Re: 583 - Prime Factors
Posted: Sat Jan 10, 2009 5:13 pm
by helloneo
fahmi wrote:can any1 help me plz??? this is the code with seive & array,but having RTE
Code: Select all
#include<stdio.h>
#include<math.h>
long long prime[3550],flag[10000],c=0,a[100000000];
a[100000000] is too big!! You can't declare that big array..
Maybe that's the reason of RTE..
Why Time Limit Exceed
Posted: Tue May 05, 2009 11:43 am
by goinglee
I've tested all the test case and all the outputs all correct, but I can not understand why I always got Time Limit Exceed....Could someone give me a great help please?? Thanks a lot!!!!!
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void Calculate_Prime(double input, long int input_sqrt)
{
int i;
for(i=2;i<=input_sqrt;i++)
{
while(fmod(input,i)==0)
{
if(input == i)
printf("%.0lf\n",input);
else
printf("%d x ",i);
input = input / i;
}
}
if(input!=1)
printf("%.0lf\n",input);
}
int InRange(double input)
{
return (abs(input)<2147483648)?1:0;
}
int main()
{
double input_num;
freopen("583.in","r",stdin);
while(scanf("%lf",&input_num)==1 && input_num!=0)
{
if(InRange(input_num))
{
printf("%.0lf = ",input_num);
long int input_sqrt = floor(sqrt(abs(input_num)));
if(abs(input_num)==1)
printf("%.0lf\n",input_num);
else if(input_num<0)
{
printf("-1 x ");
Calculate_Prime(-input_num, input_sqrt);
}
else
Calculate_Prime(input_num, input_sqrt);
}
}
return 0;
}
Re: 583 - Prime Factors
Posted: Tue May 05, 2009 5:27 pm
by mf
Why are you using floating-point numbers? They're very slow and totally unnecessary here.
And for this you should've got runtime error:
Ever heard of standard input/output redirection?
Re: 583 - Prime Factors
Posted: Wed May 06, 2009 7:38 am
by goinglee
mf wrote:Why are you using floating-point numbers? They're very slow and totally unnecessary here.
And for this you should've got runtime error:
Ever heard of standard input/output redirection?
Since the problem depicts that the range of the input g is -2^31 ~ 2^31, I think the double will be good for the solution. Anyway, I still got the same result TLE) if I change double to int!!
The code
has been removed and I still got Time Limit Exceed. I don't know why....
Could someone please help me the find it out? Since I've got crazy about this result. Thank you all very much.
Re: 583 - Prime Factors
Posted: Wed May 06, 2009 12:18 pm
by mf
Well, for a start you should avoid dividing by even numbers (except 2) in this loop:
for(i=2;i<=input_sqrt;i++)
and update input_sqrt after every successful division, so that it'll finish more quickly.
If this doesn't help, try to precompute all primes up to sqrt(2^31) = 46340 and divide in the loop only by these primes.
Since the problem depicts that the range of the input g is -2^31 ~ 2^31,
So what? Range of int is [-2^31, 2^31-1], it's enough to store the input.
I think the double will be good for the solution.
Double is almost never a good idea when you're dealing with integers. Use long long (a 64-bit integer) when range of 32-bit integers isn't enough.
Re: 583 - Prime Factors
Posted: Thu May 07, 2009 3:26 am
by goinglee
Yeah, I've solved this problem by just fixing double to int....Thank you very much!!
Re: 583 - Prime Factors
Posted: Wed Aug 05, 2009 10:26 am
by asif_khan_ak_07
I am getting TLE .....plz help
Code: Select all
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main()
{
//freopen("583.txt","r",stdin);
long int in,ans[100],ns,temp,t,r;
while((scanf("%d",&in)==1))
{
if(in==0)
exit(0);
t=0;
ns=0;
r=in;
printf("%ld = ",r);
if(in<0)
{
in=-in;
printf("%d",-1);
t++;
}
temp=in;
for(long int i=2;i<=sqrt(temp);i++)
{
if(in%i==0)
{
while(in%i==0)
{
in=in/i;
ans[ns]=i;
ns++;
}
}
//printf("%d ",i);
}
if(in>1)
{
ans[ns]=in;
ns++;
}
for(int j=0;j<ns;j++)
{
if(t++)
printf(" x ");
printf("%ld",ans[j]);
}
printf("\n");
}
return 0;
}
Re: 583 - Prime Factors
Posted: Wed Aug 05, 2009 10:53 am
by mf
sqrt() is a quite expensive function. And in this line you're calling it once in every iteration of your loop:
for(long int i=2;i<=sqrt(temp);i++)
Either precompute it (and don't forget to update precomputed value after successful division), or replace with much cheaper integer multiplication:
Code: Select all
for (int i = 2; i * i <= temp; i++)
//freopen("583.txt","r",stdin);
Use standard input/output redirection instead of freopen. It saves your time. Really.
plz help
Please use proper capitalization and spelling. This isn't sms or twitter, there's no excuse for mutilating English words like that! And this isn't the first time I'm telling you about your spelling!
583>>>Need some critical input....getting WA
Posted: Sat Aug 22, 2009 11:49 pm
by layesh
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
#define max 10000000
bool flag[max];
long arr[10000000];
void sieve(){
long i,j,k=sqrt(double(max));
flag[0]=true;
flag[1]=true;
for(i=4;i<=max;i+=2)flag=true;
for(i=3;i<=k;i+=2)if(!flag)for(j=i+i;j<=max;j+=i)flag[j]=true;
}
int main(){
long a,d,l,m,n,x,ii,jj,tos1;
freopen("583.txt","r",stdin);
sieve();
jj=0;
for(ii=0;ii<max;ii++){
if(!flag[ii]){
arr[jj]=ii;
jj++;
}
}
while(scanf("%ld",&a)==1 && a!=0){
printf("%ld =",a);
if(a<0){
m=-(a);
printf(" -1 ");
}
else m=a;
tos1=sqrt(m);
l=0;
d=m;
n=0;
for(x=0;;x++){
if(arr[x]>tos1)break;
while(1){
if((d%arr[x])==0){
n++;
if(a<0)printf("* %ld ",arr[x]);
else if(a>0 && n==1)printf(" %ld",arr[x]);
else printf(" * %ld",arr[x]);
d=d/arr[x];
while(d%arr[x]==0){
n++;
if(a<0)printf("* %ld ",arr[x]);
//else if(a>0 && n==1)printf(" %ld",arr[x]);
else printf(" * %ld",arr[x]);
d=d/arr[x];
}
if(d%arr[x]!=0)break;
}
else break;
}
}
if(d>tos1 && n>0 && a>0)printf(" * %ld",d);
else if(d>tos1 && a<0)printf("* %ld",d);
else if(d>tos1 && n==0 && a>0)printf(" %ld",d);
printf("\n");
}
return 0;
}
Re: 583 - Prime Factors
Posted: Mon Jul 12, 2010 11:51 pm
by naheed
REMOVED AFTER AC
583 why WA?
Posted: Wed Aug 04, 2010 4:59 pm
by @mjad
thanx
finally i got AC
Re: 583 - Prime Factors
Posted: Wed Aug 04, 2010 5:16 pm
by helloneo
Try Jan's test case here..
http://acm.uva.es/board/viewtopic.php?t=3170&start=101
And Please remove your code if you get AC
Re: 583 - Prime Factors
Posted: Wed Aug 04, 2010 9:56 pm
by shaon_cse_cu08
Mjad its seems like u don't take input output LIMIT seriously?? Do u?......
Each line of input will contain one number g
in the range -2^31 < g <2^31, but different of -1 and 1.
Take this inputs....
Input:
2147483647
-2147483647
-2147483648
2147483648
Output:
2147483647 = 2147483647
-2147483647 = -1 x 2147483647
(some garbage value's for last 2 inputs)
But ur code shows NOTHING...
Sundor Programmer ra input/output limit Sundor vabe ney... 