JAG Asia 2017 C-----Prime-Factor Prime(素数区间筛)

Bertha 。 2023-06-05 12:33 44阅读 0赞

### 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=ceil(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 */

转载于:https://www.cnblogs.com/CharlieWade/p/11386053.html