UVa 11408 Count DePrimes

2017-01-13 19:11:56来源:CSDN作者:SenyeLicone人点击

A number is called a DePrime if the sum of its prime factors is a prime number.
Given a and b count the number of DePrimes xi such that a ≤ xi ≤ b.
Input
Each line contains a and b in the format ‘a b’. 2 ≤ a ≤ 5000000. a ≤ b ≤ 5000000.
Input is terminated by a line containing ‘0’.
Output
Each line should contain the number of DePrimes for the corresponding test case.
Explanation:
In Test Case 2, take 10. Its Prime Factors are 2 and 5. Sum of Prime Factors is 7, which is a prime.
So, 10 is a DePrime.
Sample Input
2 5
10 21
100 120
0
Sample Output
4
9

9

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

数论+思路~

(被网上的翻译坑得好惨,要求的是区间内质因子个数是素数的数,不是质因子之和……不过话说如果求的是区间内质因子个数之和是素数的数的话能做么?)

神奇的做法,类似于欧拉函数~

在线性筛中加上几句话,顺便求出每个数值因子的个数:如果i是a[j]的倍数,那么质因子数与i相同,再跳出循环;否则就是i的质因子数再加上a[j]的质因子数,因为两个数都是质数嘛。


#include<cstdio>int n,m,a[5000001],num[5000001],tot[5000001];bool b[5000001];void findd(){	for(int i=2;i<=5000000;i++)	{		if(!b[i]) a[++a[0]]=i,tot[i]=i;		for(int j=1;a[j]*i<=5000000 && j<=a[0];j++)		{			b[i*a[j]]=1;			if(!(i%a[j]))			{				tot[a[j]*i]=tot[i];break;			}			tot[a[j]*i]=tot[i]+a[j];		}		num[i]=num[i-1]+!b[tot[i]];	}}int main(){	findd();	while(scanf("%d",&n)==1 && n)	{		scanf("%d",&m);		printf("%d/n",num[m]-num[n-1]);	}	return 0;}


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台