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 » Sat Dec 08, 2012 8:40 am

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 » Sun Apr 28, 2013 12:05 am

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 » Fri May 17, 2013 3:59 am

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 » Sat Sep 21, 2013 12:06 am

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 » Mon Sep 23, 2013 10:20 pm

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 » Tue Nov 26, 2013 12:37 am

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 » Sat Apr 26, 2014 7:01 pm

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 » Mon Apr 28, 2014 7:39 pm

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 » Sun Jun 15, 2014 5:51 am

#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 » Mon Jun 16, 2014 8:58 pm

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 » Wed Sep 03, 2014 10:24 am

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 » Wed Sep 03, 2014 6:56 pm

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 » Thu Sep 04, 2014 1:43 am

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 583 - Prime Factors

Post by lighted » Thu Sep 04, 2014 2:25 am

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)”