I have been trying this problem which is from a past hacker cup.I am
getting wrong answer.http://www.spoj.pl/problems/NFACTOR/
My approach:
1.Count the number of prime factors of a number(trivial way)
for(int i=2;i*2<=1000000;i++) number_of_factors[i]=1; //atleast 1 factor
that is 2
for(int i=3;i<=1000000/2;i+=2) {
if(!prime[i]) continue;
number_of_factors[i]=1; //it is a prime so number of factors=1;
for(int j=2;i*j<=1000000;j++){ number_of_factors[i*j]++; //increment number
of factors for i*j
prime[i*j]=false;
}
}
2. Seperately count numbers with j factors for all j in range(1,10) for
each i belonging to range(2,1000000)
3.Finding the cumalative sum for all i in range 3,1000000 for all possible
factors 1 to 10
------------------------------------------------->THE CODE
<----------------------------------------------------------------
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#define PR(x) printf(#x"=%d\n",x)
#define READ2(x,y) scanf("%d %d",&x,&y)
#define REP(i,a) for(int i=0;i<a;i++)
#define READ(x) scanf("%d",&x)
#define PRARR(x,n) for(int i=0;i<n;i++)printf(#x"[%d]=\t%d\n",i,x[i])
using namespace std;
int numFactors[1000001];
bool prime[1000001];
int numFac[10][1000001];
int main() {
for(int i=0;i<10;i++) memset(numFac[i],0,sizeof(int)*1000001);
memset(numFactors,0,sizeof(numFactors[0])*1000001);
memset(prime,1,sizeof(prime[0])*1000001);
assert(0);
numFactors[2]=1;
for(int k=2;k*2<=1000000;k++) {prime[k*2]=false;numFactors[k*2]=1;}
for(int i=3;i<1000000/2+1;i+=2){
if(prime[i]==false)continue;
numFactors[i]=1;
for(int j=2;j*i<=1000000;j++){
numFactors[j*i]++;
prime[i*j]=false;
}
}
numFactors[1]=0;
//PRARR(numFactors,100);
for(int i=2;i<=1000000;i++)
if(numFactors[i]<=10)numFac[numFactors[i]-1][i]=1;
for(int k=0;k<10;k++) for(int i=3;i<1000001;i++)
numFac[k][i]+=numFac[k][i-1];
long long t;
scanf("%lld",&t);
int a,b,n;
while(t--){
scanf("%d %d %d",&a,&b,&n);
if(n==0) {
if(a==1) printf("1\n");
else printf("0\n");
continue;
}
int ans=numFac[n-1][b]-numFac[n-1][a];
if(numFactors[a]==n) ans++;
printf("%d\n",ans);
}
}
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
