884 - Factorial Factors

[htl]

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

[Evan Tsang]

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]

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.

[sumankar]

Hi,

Can I have some i/o please?

Regards,
Suman.

[Raj Ariyan]

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

[I LIKE GN]

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

[marcadian]

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]

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

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

[jainal uddin]

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]

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

plz hlep..

[joy]

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

[Observer]

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.

[soth]

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]

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