Try precalculation..Neli wrote:I modified the sieve code,but still getting TLE.
what can I do?
884  Factorial Factors
Moderator: Board moderators
Re: TLE in884
Here's my code of 884:
#include <stdio.h>
#include <math.h>
#define SZ 1000010
char flag[SZ];
long long power[SZ],prime[SZ],c=0;
void sieve(void)
{
long long i,j,k;
for(i=3;i<SZ;i+=2)
flag='1';
prime[c++]=2;
for(i=3;i<SZ;i+=2)
{
if(flag=='1')
{
prime[c++]=i;
if(SZ/i>i)
{
k=i<<1;
for(j=i*i;j<SZ;j+=k)
flag[j]='0';
}
}
}
}
long long prime_fact(long long no)
{
long long i,count=0,root;
root=sqrt(no);
for(i=0;i<=c;i++)
{
if(prime>root)
break;
if(no%prime==0)
{
while(no%prime==0)
{
count++;
no/=prime;
}
}
root=sqrt(no);
}
if(no>1)
count++;
return count;
}
void main()
{
long long n,i,temp;
sieve();
power[1]=0;
for(i=2;i<SZ;i++)
{
temp=i;
power[temp]=power[temp1]+prime_fact(temp);
}
while(scanf("%lld",&n)==1)
{
printf("%lld\n",power[n]);
}
}
#include <stdio.h>
#include <math.h>
#define SZ 1000010
char flag[SZ];
long long power[SZ],prime[SZ],c=0;
void sieve(void)
{
long long i,j,k;
for(i=3;i<SZ;i+=2)
flag='1';
prime[c++]=2;
for(i=3;i<SZ;i+=2)
{
if(flag=='1')
{
prime[c++]=i;
if(SZ/i>i)
{
k=i<<1;
for(j=i*i;j<SZ;j+=k)
flag[j]='0';
}
}
}
}
long long prime_fact(long long no)
{
long long i,count=0,root;
root=sqrt(no);
for(i=0;i<=c;i++)
{
if(prime>root)
break;
if(no%prime==0)
{
while(no%prime==0)
{
count++;
no/=prime;
}
}
root=sqrt(no);
}
if(no>1)
count++;
return count;
}
void main()
{
long long n,i,temp;
sieve();
power[1]=0;
for(i=2;i<SZ;i++)
{
temp=i;
power[temp]=power[temp1]+prime_fact(temp);
}
while(scanf("%lld",&n)==1)
{
printf("%lld\n",power[n]);
}
}
RE  Help :(
I am at a loss as to why I am getting a Runtime Error. Please tell me what the problem is. I shall be eternally grateful.
REMOVED CODE BECAUSE IT WAS ACCEPTED[/b]
Last edited by abhiramn on Sat May 26, 2007 8:26 pm, edited 1 time in total.
Thanks
Thanks a ton for that reply. Anyways, can you tell me why that happened. Have have quite a few accepted codes where I have declared big arays in main itself.
Did this happen because I declared too many big arrays in main.
Abhiram
Did this happen because I declared too many big arrays in main.
Abhiram
Re: 884  Factorial Factors
I saw many replies about improving the speed. My Java program precalculated all the answers, but still took 2.6sec at first. After using StringBuilder as a buffer to store the output instead of outputting right away, it took about 0.6sec. That means most of the time goes into the output routine and not the real calcuations. Looks like the test set is extremely large.

 Learning poster
 Posts: 84
 Joined: Fri Jan 09, 2009 4:37 pm
 Location: IRAN
Re: 884  Factorial Factors
Code: Select all
REMOVED
after help of Chirag Chheda
Last edited by vahid sanei on Tue Apr 14, 2009 6:45 pm, edited 2 times in total.
Impossible says I`m possible

 Learning poster
 Posts: 74
 Joined: Sat Jun 21, 2008 12:24 pm
 Location: India
Re: 884  Factorial Factors
use sieve and try to compute everything within the sieve function.

 Learning poster
 Posts: 84
 Joined: Fri Jan 09, 2009 4:37 pm
 Location: IRAN

 Learning poster
 Posts: 74
 Joined: Sat Jun 21, 2008 12:24 pm
 Location: India
Re: 884  Factorial Factors
Yes.
Since in your program u are not precomputing all the prime numbers before taking the input which increases your time a lot.
Since in your program u are not precomputing all the prime numbers before taking the input which increases your time a lot.