583 - Prime Factors

[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");
	}
}

[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;
}

[helloneo]

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

[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;
}

[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:

Code: Select all

freopen("583.in","r",stdin);

Ever heard of standard input/output redirection?

[goinglee]

Why are you using floating-point numbers? They're very slow and totally unnecessary here.

And for this you should've got runtime error:

Code: Select all

freopen("583.in","r",stdin);

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

Code: Select all

freopen("583.in","r",stdin);

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.

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

[goinglee]

Yeah, I've solved this problem by just fixing double to int....Thank you very much!!

[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;

}

[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!

[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;

}

[naheed]

REMOVED AFTER AC

[@mjad]

thanx
finally i got AC

[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

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