884  Factorial Factors
Moderator: Board moderators
884  Factorial Factors
I got AC at such a really slow speed. Could someone give your suggetion about speeding up the program?

 New poster
 Posts: 11
 Joined: Sun Jan 02, 2005 9:14 am
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.
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/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

 Learning poster
 Posts: 70
 Joined: Sat Feb 05, 2005 9:38 am
 Location: Gurukul
Input/Output
Hi,
You can check this input.
Input :
You can check this input.
Input :
Output :2
10
100
1000
10000
100000
1000000
999999
9999
123487
32227
888888
123121
121312
12121
5657
1231
5
5655
Hope it helps. Bye1
15
239
2877
31985
343614
3626619
3626607
31977
426671
107204
3215736
425376
418966
39033
17699
3581
5
17693
Some Love Stories Live Forever ....

 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
please HELPPPPPPPPPPPPPPPPP
P.S. i amm used some percalc then O(1) indexing
please HELPPPPPPPPPPPPPPPPP
P.S. i amm used some percalc then O(1) indexing
There are two tragedies in life one is to lose your hearts' desire and another is to gain it  GBS.
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;
readln(n);
for i:=1 to n do
sum:=sum+faktor[i];
writeln(sum);
end;
end.

 New poster
 Posts: 6
 Joined: Thu Jul 27, 2006 2:42 pm
884:TLE, help pleaseeeeeeeeeeeeeeeee
# 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;
}
# 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;
}

 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;
}
# 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;
}
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.
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
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:
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
TLE in884
I modified the sieve code,but still getting TLE.
what can I do?
what can I do?