583 - Prime Factors

[brianfry713]

print x not *

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

That code is TLE. You can see the reason for a Compile Error by clicking "My Submissions".

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

[brianfry713]

I don't know of a way to compare only Java run times, but maybe Felix Halim could update uhunt to allow that.

[brianfry713]

Use a sieve to precompute a list of primes.

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

Doesn't match the sample I/O

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

Use the sieve to precompute the primes.

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

Don't read from a file.

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

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