当前位置: 代码迷 >> 综合 >> UVa 11408 Count DePrimes
  详细解决方案

UVa 11408 Count DePrimes

热度:75   发布时间:2024-01-19 02:31:41.0
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],因为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;
}


  相关解决方案