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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 583 - Prime Factors

Post by brianfry713 »

print x not *
Check input and AC output for thousands of problems on uDebug!

shuza
New poster
Posts: 4
Joined: Fri May 04, 2012 1:59 am

Re: 583 - Prime Factors

Post by shuza »

i am getting CE!!! i can't understand why??

Code: Select all

#include <stdio.h>
#include <math.h>

int main()
{
    long N;
    while(scanf("%ld", &N))
    {
        if(N == 0)
            break;
        printf("%ld = ", N);
        if(N < 0)
        {
            printf("-1 x ");
            N = -N;
        }
        long sq = sqrt(N);
        int factor[10000], l = 0, i;
        while(N % 2 == 0)
        {
            factor[l++] = 2;
            N /= 2;
        }
        for(i = 3; i <= sq; i += 2)
        {
            while(N % i == 0)
            {
                factor[l++] = i;
                N /= i;
            }
        }
        if(N != 1)
            factor[l++] = N;
        for(i = 0; i < l; i++)
        {
            printf("%d ", factor[i]);
            if(i != l-1)
                printf("x ");
        }
        printf("\n");
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 583 - Prime Factors

Post by brianfry713 »

That code is TLE. You can see the reason for a Compile Error by clicking "My Submissions".
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 583 - Prime Factors

Post by raj »

I need a suggestion!!!!!!!!!!
i am a java coder for that i cant compare my run time with other coders :( because most of here are from c++

so can i see only java coders run time for a specific problem !!!!
if i can then how ...?? :(

for example in this problem my java accepted run time is 1.089 sec ..

now how i can be sure that my algorithm is efficient ??? :cry:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 583 - Prime Factors

Post by brianfry713 »

I don't know of a way to compare only Java run times, but maybe Felix Halim could update uhunt to allow that.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 583 - Prime Factors TLE !!

Post by brianfry713 »

Use a sieve to precompute a list of primes.
Check input and AC output for thousands of problems on uDebug!

Aritra
New poster
Posts: 1
Joined: Sat Apr 26, 2014 6:53 pm

uva 583

Post by Aritra »

why I am getting RE?
the prob no is 583.
here is my code
#include<stdio.h>
#include<math.h>
int main()
{
int number,i,temp;
while(scanf("%d",&number)==1){
if(number<0)
{
printf("%d = -1 x ",number);
number=number*-1;
}
if(number==0)
break;
else
{
printf("%d = ",number);
}
for(i=2;i*i<=number;i++)
{
if(number%i==0)
{
printf("%d x ",i);
number=number/i;
temp=i;
i=1;
}
}
printf("%d\n",number);
}
return 0;

}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: uva 583

Post by brianfry713 »

Doesn't match the sample I/O
Check input and AC output for thousands of problems on uDebug!

roif93
New poster
Posts: 1
Joined: Sun Jun 15, 2014 5:45 am
Location: Bangladesh

Re: 583 - Prime Factors

Post by roif93 »

#include<stdio.h>
#include<math.h>
int main()
{
long long int g,i,f[100],num,j,s;
while(scanf("%lld",&g)!=EOF)
{
if(g==0)
break;
if(g<0)
{
num=g*(-1);
}
else
num=g;
i=2;
j=0;
s=sqrt(num);
while(i<=num)
{
if(i>s && j==0)
{
f[j++]=num;
break;
}
if(num%i!=0)
i++;
else
{
f[j++]=i;
num=num/i;
}
}
printf("%lld = ",g);
if(g<0)
printf("-1 x ");
for(i=0;i<j;i++)
{
printf("%lld",f);
if(i<j-1)
printf(" x ");
}
printf("\n");
}
return 0;
}



getting TLE..need some critical inputs...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 583 - Prime Factors

Post by brianfry713 »

Use the sieve to precompute the primes.
Check input and AC output for thousands of problems on uDebug!

AbyssalGreed
New poster
Posts: 9
Joined: Mon Aug 25, 2014 5:25 am

Re: 583 - Prime Factors

Post by AbyssalGreed »

Here's another problem I tried in java and the OJ gives me TLE...
is there any way you can make this run faster??
any help will be much appreciated.. thanks in advance :)

Code: Select all

import java.lang.*;
import java.math.*;
import java.util.*;
import java.text.*;

class Main
{
	public static void main(String args[])throws Exception
	{
		Scanner sc = new Scanner(new File("input.txt"));
		ArrayList<Long> primes = new ArrayList<Long>();
		while(sc.hasNext())
		{
			long num = sc.nextLong();
			long temp=0;
				temp = num;
			
			if(num==0)
				break;
			
			System.out.print(temp+" = ");
			if(num<=-2)
			{
				num = Math.abs(num);
				System.out.print("-1 x ");
			}	
				
			for(long a=2; a<=num; a++)
			{
				if(num%a==0)
				{
					primes.add(primes.size(), a);
					num = num/a;
					a--;
				}
			}
		
			for(int a=0; a<primes.size(); a++)
			{
				System.out.print(primes.get(a));
				if(a<primes.size()-1)
					System.out.print(" x ");
			}System.out.println();
			primes.clear();
			
			
		}
	}
	
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 583 - Prime Factors

Post by brianfry713 »

Don't read from a file.
Check input and AC output for thousands of problems on uDebug!

AbyssalGreed
New poster
Posts: 9
Joined: Mon Aug 25, 2014 5:25 am

Re: 583 - Prime Factors

Post by AbyssalGreed »

I remove the Scanner sc = new Scanner(new File("input.txt")); and change it to system.in before I submitted it to UVA, it's still giving me TLE, is there any way I can speed up running this code?


thanks!!

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 583 - Prime Factors

Post by lighted »

You can run your loop until sqrt(num) because all its prime factors will be less or equal to sqrt(num). After that if num is still greater than 1 then its prime.

Code: Select all

long q = Math.sqrt(num) + 1e-8;

for(long a = 2; a <= q; a++)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 5 (500-599)”