C: Prime-Factor Prime
时间限制: 1 Sec 内存限制: 128 MB
题目描述
A positive integer is called a "prime-factor prime" when the number of its prime factors is prime. For example, 12 is a prime-factor prime because the number of prime factors of 12=2×2×3 is 3, which is prime. On the other hand, 210 is not a prime-factor prime because the number of prime factors of 210=2×3×5×7 is 4, which is a composite number.
In this problem, you are given an integer interval [l,r]. Your task is to write a program which counts the number of prime-factor prime numbers in the interval, i.e. the number of prime-factor prime numbers between l and r, inclusive.
输入
The input consists of a single test case formatted as follows.
l r
A line contains two integers l and r (1≤l≤r≤109), which presents an integer interval [l,r]. You can assume that 0≤r−l<1,000,000.
输出
Print the number of prime-factor prime numbers in [l,r].
样例输入
1 9
样例输出
4
题目大意：
给一个区间[l,r],求区间中满足素因子个数也是素数的数的个数。
12=2×2×3 ------ 3个素因子，3是素数，所以12满足条件
210=2×3×5×7 --- 4个素因子，4不是素数，所以210不满足条件
AC代码：
1 /*
2 *只有合数才可能满足题目要求
3 *任何一个合数n必定包含一个不超过sqrt（n）的素因子
4 */
5
6
7 #include <bits/stdc++.h>
8 using namespace std;
9 typedef long long ll;
10 const int maxn=33000;
11 int prime[maxn+1];
12 bool isPrime[maxn+1];
13 void get_prime(int num)
14 {
15 memset(isPrime,false,sizeof(isPrime));
16 memset(prime,0,sizeof(prime));
17 for(int i=2; i<=num; ++i)
18 {
19 if(!prime[i])prime[++prime[0]]=i,isPrime[i]=true;
20 for(int j=1; j<=prime[0]&&prime[j]<=num/i; ++j)
21 {
22 prime[prime[j]*i]=1;
23 if(i%prime[j]==0)break;
24 }
25 }
26 }
27 int arr[1000007];//存区间数
28 int num[1000007];//存区间数的素因子个数
29 int main()
30 {
31 int a,b;
32 scanf("%d%d",&a,&b);
33 int len=b-a+1;
34 for(int i=1; i<=len; ++i)
35 {
36 arr[i]=a+i-1;
37 }
38 int m=sqrt(b);
39 get_prime(m);
40 int ans=0;
41 for(int i=1; i<=prime[0]; ++i)
42 {
43 int lef=ceil(a*1.0/prime[i]);
44 int rig=b*1.0/prime[i];
45 for(int j=lef; j<=rig; ++j)
46 {
47 /*
48 *只有合数才可能满足题目要求
49 *j*prime[i]必为合数
50 */
51 int pos=j*prime[i]-a+1;
52 while(arr[pos]%prime[i]==0)
53 {
54 arr[pos]/=prime[i];
55 ++num[pos];
56 }
57 }
58 }
59 // for(int i=1;i<=len;++i)
60 // {
61 // cout<<arr[i]<<endl;
62 // //if((arr[i]==1&&isPrime[num[i]])||(arr[i]>1&&isPrime[num[i]+1]))++ans;
63 // }
64 // system("pause");
65 for(int i=1;i<=len;++i)
66 {
67 if((arr[i]==1&&isPrime[num[i]])||(arr[i]>1&&isPrime[num[i]+1]))++ans;
68 //arr[i]==1&&isPrime[num[i]] 的情况是素因子都小于sqrt（b）
69 //arr[i]>1&&isPrime[num[i]+1] 的情况就是有一个素因子是大于srtq（b）的，素因子个数直接加一就好了
70 }
71 printf("%d\n",ans);
72 return 0;
73 }
74 /*
75 1 9
76
77
78 100000000 101000000
79 */
JAG Asia 2017 C-----Prime-Factor Prime(素数区间筛)
原文：https://www.cnblogs.com/CharlieWade/p/11386053.html
