884 - Factorial Factors

[marco2509]

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



[seraph]

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


[fkrafi]

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


[@mjad]

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



[sazzadcsedu]

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.

[@mjad]

Thanks for your reply
i am trying to understand.
you may remove it now.

[@mjad]

i don't understand properly ?
so concept not clear .
Please discuss your Code

thanks for your help

[Bamzi]

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?

[Scarecrow]

getting TLE. can't make the code faster. can someone help me plz

Code: Select all

AC


[brianfry713]

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

[Scarecrow]

thanks i used a simple DP and your hint of the relation between the results of n and n-1 was very much helpful