## 884 - Factorial Factors

Moderator: Board moderators

marco2509
New poster
Posts: 3
Joined: Wed Oct 28, 2009 10:59 pm

### Re: 884 - Factorial Factors

I need help with my code, I don't know where is the mistake, I received "Factorial Factors has failed with verdict Time limit exceeded". I think is the input.

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

using namespace std;
long int *array;

void primos(long int numero)
{
int factor = 2;
while(numero >= factor*factor) {
if(!(numero % factor)) {
array[factor]++;
numero = numero / factor;
continue;
}
if(factor == 2) factor++;
else factor += 2;
}
array[numero]++;

}

int principal()
{
long int numero;
int factor;
long int res=0;
char line;

printf("Introduce un numero entero: ");
gets(line);
numero= (long int) atoi(line);
if(numero==0)
return 1;
array=new long int[numero];
for(long int i = 0; i <= numero; ++i) array[i] = 0;
for(long int i = 2; i <= numero; ++i)
primos(i);
for(long int i = 2; i <= numero; ++i)
if(array[i]!=0)
res=res+array[i];
printf("%ld\n",res);
return 0;

}

int main() {
while (principal()==0)
delete array;
return 0;
}

``````

seraph
New poster
Posts: 9
Joined: Tue Dec 15, 2009 4:18 pm

### Re: 884 - Factorial Factors

where is my mistake in this program?
i always got TLE

Code: Select all

``````#include <iostream>
#include <vector>
using namespace std;
int arr={0};
vector<int> v;
int main()
{
bool prime={0};
prime=1;
prime=1;
for (int i=2;i<=1000000;i++)
{
if (prime[i]==0)
{
v.push_back(i);
int temp=i+i;
while (temp<=1000000)
{
prime[temp]=1;
temp+=i;
}
}
}

int count=0;

int n;
while (cin>>n)
{
count=0;
int total=0;
for (int i=2;i<=n;i++)
{
if (arr[i]!=0)
{
total+=arr[i];
continue;
}
if (prime[i]==0)
{
arr[i]=1;
//cout<<" 1 ";
total++;
continue;
}
count=0;
int temp=i,j=0;

while (temp!=1)
{
if (arr[temp]>0)
{
count+=arr[temp];
break;
}
if (temp%v[j]==0)
{
temp/=v[j];
count++;
}
else
j++;
}
//cout<<"count : "<<count;
total+=count;
arr[i]=count;
}

cout<<total<<endl;
}
return 0;
}
``````

fkrafi
New poster
Posts: 13
Joined: Wed Sep 15, 2010 1:36 pm

### Re: 884 - Factorial Factors (WHY TLE)

Code: Select all

``````#include<stdio.h>
#include<math.h>
int prime, prm, sz;

void sieve(int n)
{
prime=1;
prime=1;
int m = int(sqrt(n)), i=2, k;
for(k=i*i; k<=n; k+=i)
prime[k]=1;
for (i=3; i<=m; i+=2)
if(!prime[i])
for (k=i*i; k<=n; k+=i)
prime[k]=1;
}
void only_primes()
{
prm = 2;
sz = 1;
for(int i=3; i<=1000010; i+=2)
if(!prime[i])
prm[sz++] = i;
}

long int no_prime(long int n)
{
int i, t;
long int cnt=0;
for(i=0; (i<sz && prm[i]<=n); i++)
{
t = n;
while(t/prm[i])
{
cnt += (t/prm[i]);
t /= prm[i];
}
}
return cnt;
}

int main()
{
int n;
long int res;
sieve(1000010);
only_primes();
while(scanf("%d", &n) != EOF)
{
res = no_prime(n);
printf("%ld\n", res);
}
return 0;
}
``````

New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

Here is my code I think this is so efficient

Code: Select all

``````#include<stdio.h>

#define M 1000002

int *prime =new int[M];
long *pre =new long[M];

int isprime()
{
long i,j;
for(i=0;i<M;i++)
{
pre[i]=prime[i]=0;
}
for(i=2;i*i<=M-2;i++)
if(!prime[i])
for(j=i+i;j<=M-2;j+=i)
prime[j]=1;
return 0;
}

long divsor(long n)
{
long d,total=0,i,j;
j=n;
for(i=2;i*i<=n;i++)
{
if(!prime[i])
{
d=0;
if(pre[n/i]!=0&&n%i==0)
{
pre[j]=pre[n/i]+1;
return pre[j];
}

while(n%i==0)
{
d++;
n/=i;
}
total+=d;
}

}
if(n!=1)
total++;
pre[j]=total;
}

int main()
{
long a,b,r;
int t;
t=isprime();
//freopen("884.txt","r",stdin);
while(scanf("%ld",&a)==1)
{
r=0;
for(b=2;b<=a;b++)
r+=divsor(b);
printf("%ld\n",r);
}

return 0;
}

``````

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 884 - Factorial Factors

No, I don't think so.Here is an efficient way-

Code: Select all

`````` code removed
``````
I have no time to explain my code.So its upto you to understand the code.Dont submit it without understanding.And let me know after copying so that i can remove it.
Last edited by sazzadcsedu on Tue Oct 19, 2010 10:45 pm, edited 2 times in total.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

### Re: 884 - Factorial Factors

i am trying to understand.
you may remove it now.

New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

### Re: 884 - Factorial Factors

i don't understand properly ?
so concept not clear .

Bamzi
New poster
Posts: 1
Joined: Tue Aug 30, 2011 10:15 am

### Re: 884 - Factorial Factors

what do you mean when you say to modify the sieve code? In which way? What do you want to get hotel Thailand Directory with this modification?
Last edited by Bamzi on Wed May 29, 2013 2:15 pm, edited 1 time in total.

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 884 - Factorial Factors

getting TLE. can't make the code faster. can someone help me plz Code: Select all

``````AC
``````
Last edited by Scarecrow on Sun Jun 03, 2012 10:02 pm, edited 1 time in total.
Do or do not. There is no try.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 884 - Factorial Factors

Precompute the answers for all n. Can you see a relationship between the results for n and n-1?
Check input and AC output for thousands of problems on uDebug!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 884 - Factorial Factors

thanks i used a simple DP and your hint of the relation between the results of n and n-1 was very much helpful Do or do not. There is no try.

mobarak.islam
New poster
Posts: 38
Joined: Wed Dec 05, 2012 11:29 pm

### Re: 884 - Factorial Factors

Code deleted after AC.
Last edited by mobarak.islam on Tue Jun 11, 2013 3:17 pm, edited 1 time in total.

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

### Re: 884 - Factorial Factors

Hi Mobarak, I checked your code. Change the code portion as following

Code: Select all

``````while( prime[ind]*prime[ind]<=x)
{
if(x%prime[ind] == 0)
{
x=x/prime[ind];
count++;
ind = -1;
}
ind++;
}
if(x>1) count++;
``````
You don't need to check prime[ind]<=x rather check square(prime[ind])<=x. This will reduce your complexity from N to sqrt(N). cause if prime[ind] is greater than sqrt(x) then x must not be divisible by any other prime rather than x itself(In that case x is a prime, so increment the count by 1).
Hope you understood.

mobarak.islam
New poster
Posts: 38
Joined: Wed Dec 05, 2012 11:29 pm

### Re: 884 - Factorial Factors

@t.tahasin :Thanks for your great help. I got AC Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 884 - Factorial Factors

getting tle
need help
any idea to get me out of tle

Code: Select all

``````#include<stdio.h>
#include<math.h>
bool Status={0};
long Data={0,2},Ary;

void Cal()
{
long N=7928,I,K;
for(I=3;I<1001;I+=2){
if(!Status[I]){
for(K=I*I;K<=N;K+=I+I)
Status[K]=1;
}
}
K=1;
for(I=3;I<=N;I+=2)
if(!Status[I]){
Data[++K]=I;
if(K>1000) break;
}
//printf("%ld %ld\n",I,K);
}

int main()
{
long I,K,L,M,N,A;
Cal();
for(A=2;A<1000001;A++){
L=sqrt(A);
K=0;
N=A;
for(I=1;I<=L&&N>1;I++){
//if(N%2!=0&&!Status[N]) {K++;break;}
if(A>N) {K+=Ary[N];break;}
else{
M=0;
while(N%Data[I]==0){
++M;
N/=Data[I];
if(A>N) {K+=Ary[N];N=0;break;}
}
K+=M;
}
}
Ary[A]=K;
if(A%2!=0&&K==0) Ary[A]++;
}

while(scanf("%ld",&N)==1){
K=0;
for(A=2;A<=N;A++) K+=Ary[A];
printf("%ld\n",K);
}
return 0;
}

``````
[/color]
we r surrounded by happiness
need eyes to feel it!