## 884 - Factorial Factors

Moderator: Board moderators

### 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[10];     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;}`
marco2509
New poster

Posts: 3
Joined: Wed Oct 28, 2009 10:59 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[1000001]={0};vector<int> v;int main(){    bool prime[1000001]={0};    prime[0]=1;    prime[1]=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;}`
seraph
New poster

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

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

Code: Select all
`#include<stdio.h>#include<math.h>int prime[1000010], prm[1000010], sz;void sieve(int n){   prime[0]=1;   prime[1]=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[0] = 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;}`
fkrafi
New poster

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

Here is my code I think this is so efficient
Code: Select all
`#include<stdio.h>#define M 1000002int *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;}`
New poster

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

### 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.
Experienced poster

Posts: 136
Joined: Sat Nov 29, 2008 8:01 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 .

New poster

Posts: 44
Joined: Thu Jul 22, 2010 9:42 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 levitra pro with this modification?
Bamzi
New poster

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

### 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.
Scarecrow
Learning poster

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

### Re: 884 - Factorial Factors

Precompute the answers for all n. Can you see a relationship between the results for n and n-1?
brianfry713
Guru

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

### 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.
Scarecrow
Learning poster

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

Previous