884 - Factorial Factors
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 884 - Factorial Factors
Precompute the answers for all n. Your I/O loop is taking O(n) instead of O(1) time.
Check input and AC output for thousands of problems on uDebug!
-
- 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;
}
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
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 :
My Process :
- 1. Bitwise Sieve Prime generation through 1000
2. Then Precalculate all the Result using factorization.
3. Then output.
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 .
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.
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