xtu oj 1526 奇因数

题目描述

如果一个数n，其素因子的个数为ω(n)，如果ω(n)是奇数，那么称其为“奇因数”。

比如，数60=22?3?5，ω(60)=3，那么60是“奇因数”。 显然，所有素数，必然是“奇因数”。

求区间[a,b]中“奇因数”的个数。

输入格式

第一行是一个整数T?(1≤T≤10000)，表示样例的数量。

以后每行一个样例，为两个整数a,b,1≤a≤b≤106。

输出格式

每行输出一个样例的结果，为一个整数。

样例输入

2
1 10
1 100

样例输出

7
43

AC代码

#include<stdio.h>
#define N 1000005
int a[N]={};
int f[N]={};
int w[N]={};
void init(){
	int i,j;
	a[0]=1,a[1]=1;
	for(i=2;i*i<=N;i++){
		if(a[i]==0){
			for(j=2*i;j<N;j+=i){
				a[j]=1;
			}
		}
	}
	for(i=2;i<=N;i++){
		if(a[i]==0){
			w[i]=1;
			for(j=2;i*j<=N;j++){
				w[i*j]++;
			}
		}
	}
	for(i=2;i<=N;i++){
		if(w[i]%2!=0){
			f[i]=1;
		}
	} 
	for(i=1;i<N;i++){
		f[i]+=f[i-1];
	}
}
void sol(){
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d\n",f[b]-f[a-1]);
}
int main(){
	int T;
	scanf("%d",&T);
	init();
	while(T--){
	  sol();
	}
}

求质因数的个数，利用f[i*j]++，例如f[2]=1,则f[2*3]=1,f[3]=1,f[3*2]=f[6]++=2。求幂次次数，利用f[i*j]=f[i]+f[j]。例如f[2]=1,f[4]=f[2]+f[2]=2。