583 - Prime Factors

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

fahmi
New poster
Posts: 7
Joined: Sat Nov 22, 2008 9:10 am

Re: 583 - Prime Factors

Post by fahmi » Sat Jan 10, 2009 4:49 pm

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
New poster
Posts: 7
Joined: Sat Nov 22, 2008 9:10 am

Re: 583 - Prime Factors

Post by fahmi » Sat Jan 10, 2009 4:51 pm

& 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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 583 - Prime Factors

Post by helloneo » Sat Jan 10, 2009 5:13 pm

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

goinglee
New poster
Posts: 5
Joined: Tue Apr 07, 2009 7:37 am

Why Time Limit Exceed

Post by goinglee » Tue May 05, 2009 11:43 am

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!!!!! :cry:

#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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 583 - Prime Factors

Post by mf » Tue May 05, 2009 5:27 pm

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
New poster
Posts: 5
Joined: Tue Apr 07, 2009 7:37 am

Re: 583 - Prime Factors

Post by goinglee » Wed May 06, 2009 7:38 am

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:

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 583 - Prime Factors

Post by mf » Wed May 06, 2009 12:18 pm

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
New poster
Posts: 5
Joined: Tue Apr 07, 2009 7:37 am

Re: 583 - Prime Factors

Post by goinglee » Thu May 07, 2009 3:26 am

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

asif_khan_ak_07
New poster
Posts: 25
Joined: Fri Apr 17, 2009 8:24 am

Re: 583 - Prime Factors

Post by asif_khan_ak_07 » Wed Aug 05, 2009 10:26 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 583 - Prime Factors

Post by mf » Wed Aug 05, 2009 10:53 am

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
New poster
Posts: 5
Joined: Wed Jun 10, 2009 10:13 pm

583>>>Need some critical input....getting WA

Post by layesh » Sat Aug 22, 2009 11:49 pm

#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
New poster
Posts: 8
Joined: Sun Oct 25, 2009 7:20 pm

Re: 583 - Prime Factors

Post by naheed » Mon Jul 12, 2010 11:51 pm

REMOVED AFTER AC

@mjad
New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

583 why WA?

Post by @mjad » Wed Aug 04, 2010 4:59 pm

thanx
finally i got AC
Last edited by @mjad on Thu Aug 12, 2010 10:08 am, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 583 - Prime Factors

Post by helloneo » Wed Aug 04, 2010 5:16 pm

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

User avatar
shaon_cse_cu08
New poster
Posts: 50
Joined: Tue May 25, 2010 9:10 am
Contact:

Re: 583 - Prime Factors

Post by shaon_cse_cu08 » Wed Aug 04, 2010 9:56 pm

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... :lol:
I'll keep holding on...Until the walls come tumbling down...And freedom is all around ..... :x

Post Reply

Return to “Volume 5 (500-599)”