## 884 - Factorial Factors

Moderator: Board moderators

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

### Re: 884 - Factorial Factors

Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Not getting the required output

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 884 - Factorial Factors

Even if you find what's wrong with your code you'll get TLE.
brianfry713 wrote:Precompute the answers for all n. Your I/O loop is taking O(n) instead of O(1) time.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

ssavi
New poster
Posts: 28
Joined: Thu Nov 20, 2014 9:57 pm

### Re: 884 - Factorial Factors

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;
}
``````
I know I am a Failure Guy .

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 884 - Factorial Factors

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]``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman