884 - Factorial Factors

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 884 - Factorial Factors

Post by marco2509 » Wed Oct 28, 2009 11:08 pm

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
New poster
Posts: 9
Joined: Tue Dec 15, 2009 4:18 pm

Re: 884 - Factorial Factors

Post by seraph » Wed Jan 13, 2010 5:42 pm

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
New poster
Posts: 13
Joined: Wed Sep 15, 2010 1:36 pm

Re: 884 - Factorial Factors (WHY TLE)

Post by fkrafi » Wed Oct 06, 2010 7:54 pm

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
New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

Why 884 TL? I don't know. please help me

Post by @mjad » Tue Oct 19, 2010 2:27 pm

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
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 884 - Factorial Factors

Post by sazzadcsedu » Tue Oct 19, 2010 10:03 pm

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
For Hints: http://salimsazzad.wordpress.com

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

Re: 884 - Factorial Factors

Post by @mjad » Tue Oct 19, 2010 10:12 pm

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

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

Re: 884 - Factorial Factors

Post by @mjad » Wed Oct 20, 2010 4:55 am

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

thanks for your help

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

Re: 884 - Factorial Factors

Post by Bamzi » Tue Aug 30, 2011 10:16 am

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

Post by Scarecrow » Fri Jun 01, 2012 12:16 am

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

Post by brianfry713 » Fri Jun 01, 2012 11:53 pm

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

Post by Scarecrow » Sun Jun 03, 2012 10:01 pm

thanks :D 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

Post by mobarak.islam » Tue Jun 11, 2013 2:26 pm

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

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

Post by t.tahasin » Tue Jun 11, 2013 2:35 pm

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

Post by mobarak.islam » Tue Jun 11, 2013 3:16 pm

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

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 884 - Factorial Factors

Post by mahade hasan » Thu Oct 31, 2013 10:01 pm

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]
we r surrounded by happiness
need eyes to feel it!

Post Reply

Return to “Volume 8 (800-899)”