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 hotel Thailand Directory 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

[mobarak.islam]

I'm getting TLE here. Someone please help me.

Code deleted after AC.

[t.tahasin]

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]

@t.tahasin :Thanks for your great help. I got AC

[mahade hasan]

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

Code: Select all

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

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]