884 - Factorial Factors

[brianfry713]

Precompute the answers for all n. Your I/O loop is taking O(n) instead of O(1) time.

[richatibrewal]

I am not getting the required output. Plz tell me what is the problem with the code?

Code: Select all

#include<cstdio>
#include<cmath>
#include<vector>
#define MAXLEN 1000010
using namespace std;
int mark[MAXLEN];
vector<int> prime;
void sieve()
{
    int i,j,p;
    p=(float)pow(MAXLEN,0.5);
    for(i=0;i<MAXLEN;i++)
        mark[i]=1;
    for(i=2;i<=p;i++)
    {
        if(mark[i]==1)
            for(j=i*i;j<MAXLEN;j=j+i)
                mark[j]=0;
    }
    for(i=2;i<MAXLEN;i++)
        if(mark[i]==1)
        {
            prime.push_back(i);
            //printf("%d\n",i);
        }
}
int main()
{
    sieve();
    int n,i,j,count,k;
    while(scanf("%d",&n)!=EOF)
    {
        count=0;
        for(i=0;prime[i]<=n;i++)
        {
            for(j=prime[i];j<=n;j=j*prime[i])
                count=count+(n/j);
        }
        printf("%d\n",count);
    }
    return 0;
}

[lighted]

Even if you find what's wrong with your code you'll get TLE.

Precompute the answers for all n. Your I/O loop is taking O(n) instead of O(1) time.

[ssavi]

Hi .....Anyone Please Help me .... I Got AC with a run time of 1.216 second ... But I want to get AC < 1 second ... How to design my Code or Optimize much my Algorithm .........

My Process :

• 1. Bitwise Sieve Prime generation through 1000
  2. Then Precalculate all the Result using factorization.
  3. Then output.

Here is the Code .... How to Optimize it ?? I need it Extremely . Please Help Me. Where I have to Optimize it .

Code: Select all

#include<bits/stdc++.h>
#define MAX 1000001
#define LL long long int

using namespace std;

int status[(MAX/32)+10];
int factcnt[1000005];
vector<int>primelist;

bool check(int n, int pos) { return (bool)(n & (1<<pos)); }
int SET(int n, int pos){ return n=n|(1<<pos);}

void sieve()
{
    int sqrtN=int (sqrt(MAX));
    for(int j=4; j<MAX; j=j+2)
        status[j>>5]=SET(status[j>>5],j&31);
    for(int i=3; i<=sqrtN; i=i+2)
    {
        if(check(status[i>>5],i&31)==0)
        {
            for(int j=i*i; j<=MAX; j= j + (i<<1))
            {
                status[j>>5]=SET(status[j>>5],j&31);
            }
        }
    }
    primelist.push_back(2);
    int cnt = 1;
    for(int i=3; i<=MAX; i=i+2)
    {
        if(check(status[i>>5], i&31)==0)
        {
            primelist.push_back(i);
        }
    }
}

void fact()
{
    sieve();
    factcnt[2]=1;
    for(int i=3; i<1000001; i++)
    {
        int cnt = 0;
        int sqrtN = (int) sqrt(i);
        int div = i;
        for(int j=0; primelist[j]<=sqrtN && j<169; j++)
        {
            if(div%primelist[j]==0)
            {
                while(div%primelist[j]==0)
                {
                    div = div / primelist[j];
                    cnt++;
                }
            }
        }
        if(div>1)  cnt++;
        factcnt[i]=factcnt[i-1] + cnt;
    }
}

int main()
{
    fact();
    int n;
    while(scanf("%d",&n)==1)
    {
        cout<<factcnt[n]<<endl;
    }
    return 0;
}

[lighted]

My code accepted in 0.020. My sieve is similar to yours, but it's not bitwise.
You can optimize second step. I precalculated all the results without factorization. I calculate it in O(1000000) with only one loop.

I used array cnt[1000001], instead of variable cnt.

Code: Select all

For each N from 2 to 1000000 store arbitrary prime factor of N in one array factor[1000001]. 
(This can be done during sieve generation).

For each N from 2 to 1000000

  if N is prime cnt[N] = 1
  else          cnt[N] = cnt[ N / factor[N] ] + 1 (where factor[N] is arbitrary prime factor of N)
 
  factorNumber[N] = factorNumber[N - 1] + cnt[N]