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

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

884 - Factorial Factors

Post by htl » Sun Jan 02, 2005 9:49 am

I got AC at such a really slow speed. Could someone give your suggetion about speeding up the program?

Evan Tsang
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am

Post by Evan Tsang » Wed Jan 19, 2005 11:25 am

I got accepted, not good speed also. Maybe it's because I precalculate all the solutions

I use a modifiication of sieve and calculate the number of terms as it goes.
Then for all i, calculate all the sum of terms[2] to terms..

I have the answer[] arrays before I even start reading the input.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Tue Jan 25, 2005 11:25 pm

Hello.
My algo is as fallows.I find all prime numbers in range 1..1000000(Sieve).
For all K(prime numbers in range 2..n) s+=n/k+n/k^2+n/k^3...
This work fast for test n=1000000 but for 100 such tests it works slow.
Please someone explain me some other more faster algo.
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Fri Mar 04, 2005 11:14 am

Hi,

Can I have some i/o please?

Regards,
Suman.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

Input/Output

Post by Raj Ariyan » Fri Mar 04, 2005 11:27 am

Hi,

You can check this input.

Input :-
2
10
100
1000
10000
100000
1000000
999999
9999
123487
32227
888888
123121
121312
12121
5657
1231
5
5655
Output :-
1
15
239
2877
31985
343614
3626619
3626607
31977
426671
107204
3215736
425376
418966
39033
17699
3581
5
17693
Hope it helps. Bye
Some Love Stories Live Forever ....

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

SO FASTER!!!!!!!!!!!!!!!!!!!!!!!!

Post by I LIKE GN » Tue Sep 06, 2005 9:07 pm

yaa i amm really CONFUSED how people got bellow 2 sec
please HELPPPPPPPPPPPPPPPPP
P.S. i amm used some per-calc then O(1) indexing
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

884time limit exceed (over 10 seconds)

Post by marcadian » Sun Mar 05, 2006 5:42 am

why??on my computer this code run really fast, even if the judge grader is slower than my pc, i think not over 10 seconds, here is my code

Code: Select all


const max=1000000;
        limit=max shr 1;
var     faktor:array[1..max]of longint;
        i,sum:longint;
        n:longint;

procedure generate;
var     i,j,k:longint;
begin
        for i:=1 to max do
                faktor[i]:=1;
        faktor[1]:=0;
        for i:=2 to limit  do
        begin
                k:=max div i;
                for j:=i to k do
                begin
                        faktor[i*j]:=faktor[i] + faktor[j];
                end;
        end;
end;


begin
        generate;
        while not eof do
        begin
                sum:=0;
                readln(n);
                for i:=1 to n do
                        sum:=sum+faktor[i];
                writeln(sum);
        end;
end.


jainal uddin
New poster
Posts: 6
Joined: Thu Jul 27, 2006 2:42 pm

884:TLE, help pleaseeeeeeeeeeeeeeeee

Post by jainal uddin » Sat Sep 16, 2006 2:27 pm

# include <stdio.h>
# include <math.h>
# include <string.h>
#define limit 1000000

long composite[1000001];
void seive()
{
long i, j, k, m, end;
memset(composite, 1, sizeof(composite));

for (i = 2; i <= 1000; i ++)
if (composite)
for (j = i * i; j <= limit; j += i)
composite[j] = 0;
}
int main ()
{
long i, N,count,num;
seive();
while ((scanf("%ld", &N))!=EOF)
{



count = 0;
for (i = 2;i <= 1000000; i++)
{
if (composite)
{
if( i > N )
break;
num = N;
while( num )
{
num = num / i;
count+=num;
}
}
}

printf("%ld\n",count);
}

return 0;
}

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sat Sep 30, 2006 10:46 pm

You should calculate all of the counts for each N before you take input.

jainal uddin
New poster
Posts: 6
Joined: Thu Jul 27, 2006 2:42 pm

but I have got TLE again

Post by jainal uddin » Tue Oct 03, 2006 9:07 am

my ne code is below:
# include <stdio.h>
# include <math.h>
# include <string.h>
#define limit 1000000

long composite[limit+1];
void seive()
{
long i, j, k, m, end;
memset(composite, 1, sizeof(composite));

for (i = 2; i <= sqrt(limit); i ++)
if (composite)

for (j = i * i; j <= limit; j += i)
composite[j] = 0;
}

int main ()
{
long i, N,count,num,n,fact[limit+1];
seive();
for(N = 2; N <= limit; N++)
{
count = 0;
for (i = 2;i <= limit; i++)
{
if (composite)
{
if( i > N )
break;
num = N;
while( num )
{
num = num / i;
count+=num;
}
}
}
fact[N] = count;

}
while((scanf("%ld",&n)) != EOF)
{
printf("%ld\n",fact[n]);
}

return 0;
}

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

Post by joy » Mon Dec 04, 2006 8:04 pm

I also got accepted with sloww speed, how can i speed up this problemm

plz hlep..
form kisui na ... class tai asol....
iF U hv d class u get the form....

joy
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

Post by joy » Tue Dec 05, 2006 10:31 pm

this sort of thread Encourage us to create a new thread....

bcoz every one want's to know how can speed up the program??? but no such ans!!
form kisui na ... class tai asol....
iF U hv d class u get the form....

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Dec 06, 2006 4:30 am

Well, if you use your sieve properly, then you should get runtimes below 1 second quite easily (mine is 0.36x second).

I don't know what hints I can give. I use no tricks, and my code has only 25 lines.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

Post by soth » Tue Apr 17, 2007 1:41 am

Ops... My program does all cases from Raj Ariyan well, except these ones:


1000000 --> 3626820 (output should be 3626619)

999999 --> 3626808 (output should be 3626607)

888888 --> 3215904 (it shouls be 3215736)


My algorithm, once it has all primes, does the following:

Code: Select all

factors = 0
for each prime until last prime or prime > n (where n is the input) 
     p = prime[i]
     while (n / p > 0)
             factors = factors + n / p
             p = p * prime[i]
return factors


Neli
New poster
Posts: 7
Joined: Thu May 03, 2007 8:35 am
Location: Sylhet
Contact:

TLE in884

Post by Neli » Thu May 03, 2007 8:44 am

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

Post Reply

Return to “Volume 8 (800-899)”