884 - Factorial Factors

[helloneo]

I modified the sieve code,but still getting TLE.
what can I do?

Try precalculation..

[Neli]

Thanks.But I tried!
Believe me.
Still not accepted

[soth]

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]

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]

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]

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]

[helloneo]

You can't declare a big array in a function.. it should be global

[abhiramn]

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]

please, can someone tell me wich modification should I do in sieve code?

[mmonish]

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]

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]

Code: Select all

REMOVED 
after help of Chirag Chheda 

[Chirag Chheda]

use sieve and try to compute everything within the sieve function.

[vahid sanei]

you mean Sieve of Eratosthenes ?

[Chirag Chheda]

Yes.
Since in your program u are not precomputing all the prime numbers before taking the input which increases your time a lot.