## 884 - Factorial Factors

Moderator: Board moderators

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

### 884 - Factorial Factors

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

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

yaa i amm really CONFUSED how people got bellow 2 sec
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.

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

### 884time limit exceed (over 10 seconds)

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

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

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

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

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