884 - Factorial Factors

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: TLE in884

Post by helloneo »

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:

Post by Neli »

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

soth
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:22 am

Post by 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
New poster
Posts: 7
Joined: Thu May 03, 2007 8:35 am
Location: Sylhet
Contact:

Post by 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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by 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
New poster
Posts: 29
Joined: Sat May 26, 2007 7:54 pm

RE - Help :(

Post by abhiramn »

:roll: :roll: :roll:
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

Post by helloneo »

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

Post by 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
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:22 am

Post by soth »

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

Post by 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
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 884 - Factorial Factors

Post by 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
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 884 - Factorial Factors

Post by vahid sanei »

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

Post by Chirag Chheda »

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

Post by vahid sanei »

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

Post by 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.

Post Reply

Return to “Volume 8 (800-899)”