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 » Thu May 03, 2007 5:38 pm

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 » Sun May 06, 2007 7:42 am

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 » Sun May 06, 2007 9:50 pm

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 » Wed May 09, 2007 6:55 am

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 » Wed May 09, 2007 8:38 am

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 » Sat May 26, 2007 7:58 pm

: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 » Sat May 26, 2007 8:12 pm

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 » Sat May 26, 2007 8:24 pm

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 » Tue Jun 05, 2007 12:03 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

Post by mmonish » Tue Jun 05, 2007 5:15 am

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 » Sun Sep 14, 2008 6:21 am

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.

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

Re: 884 - Factorial Factors

Post by vahid sanei » Sun Apr 12, 2009 5:20 pm

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 » Sun Apr 12, 2009 5:44 pm

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

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

Re: 884 - Factorial Factors

Post by vahid sanei » Sun Apr 12, 2009 8:11 pm

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 » Mon Apr 13, 2009 7:43 am

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