## 884 - Factorial Factors

Moderator: Board moderators

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

### Re: TLE in884

Neli wrote:I modified the sieve code,but still getting TLE.
what can I do?
Try precalculation..

Neli
New poster
Posts: 7
Joined: Thu May 03, 2007 8:35 am
Location: Sylhet
Contact:
Thanks.But I tried!
Believe me.
Still not accepted

soth
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:22 am
what do you mean when you say to modify the sieve code? In which way? What do you want to get with this modification?

Neli
New poster
Posts: 7
Joined: Thu May 03, 2007 8:35 am
Location: Sylhet
Contact:
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[temp-1]+prime_fact(temp);

}
while(scanf("%lld",&n)==1)
{
printf("%lld\n",power[n]);
}

}

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
You can try Eduard's approach.. it will get your program much faster..
But the strange thing is my approach is the same as yours, and I got AC in 3.045..

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
You can't declare a big array in a function.. it should be global

abhiramn
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

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

soth
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:22 am
please, can someone tell me wich modification should I do in sieve code?

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
Here no need of modification in sieve function. U can store the number of factors of each number in an array. Then print sum of the factors of each number upto n. After precalculation the complexity is O(1).

Hope it helps.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

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

vahid sanei
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

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

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

### Re: 884 - Factorial Factors

you mean Sieve of Eratosthenes ?
Impossible says I`m possible

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