试题 B:纯质数
本题总分：5分

【问题描述】
如果一个正整数只有1和它本身两个约数，则称为一个质数（又称素数）。前几个质数是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,…
如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如：2,3, 5, 7, 23, 37都是纯质数，而11, 13, 17, 19, 29, 31不是纯质数。当然1, 4, 35也不是纯质数。
请问，在1到20210605中，有多少个纯质数？

【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【分析】

答案：1903

暴力法

作为一个合格的暴力选手，首先想到的当然就是暴力啦！！

先逐位判断这个数的每一位是不是素数，因为0~9中也就0，1，4，6，8，9这六个数不是素数，所以拿着个数依次取每个数位上的数字来判定是否为素数。(solve函数，下同)
从2开始到20210605，依次判断每个数位上的数字是否为素数，如果不满足这个条件直接pass，如果满足了，则需要继续判定整个数是否为素数。

#include "bits/stdc++.h"
using namespace std;
bool solve(int n){
    while(n){
        int temp = n%10;
        if(temp==0||temp==1||temp==4||temp==6||temp==8||temp==9)
            return false;
        n/=10;
    }
    return true;
}
//暴力
int main() {
    int cnt = 0;
    for (int i = 2; i <= 20210605; i++) {
        if (solve(i)) {
            bool flag = false;
            for (int j = 2; j < i; j++) {
                if (i % j == 0)
                    flag = true;
            }
            if (!flag)
                cnt++;
        }
    }
    cout << cnt;
}

埃氏筛法

这是我之前看的一个数论小算法，今天再来总结一下。时间复杂度应该是O(nloglogn)。算法核心是从2开始到maxn一路往后面筛，用一个bool数组记录是否为素数。初始化全为false。

如果当前遍历的数对应为false，则把后面所有能整除这个数的数字都标为true。（例如2可以筛掉4、6、8、10…,也就是n以前所有的复数）
如果是true，意味着被标记过了，则不作操作。

#include "bits/stdc++.h"
using namespace std;
bool solve(int n){
   while(n){
       int temp = n%10;
       if(temp==0||temp==1||temp==4||temp==6||temp==8||temp==9)
           return false;
       n/=10;
   }
   return true;
}
//埃氏筛法
int maxn = 20210610;
bool p[20210610] = {false};
int main(){
   for(int i=2;i<=maxn-5;i++){
       if(!p[i]){
           for(int j = 2*i ;j<maxn-5;j+=i){
               p[j] = true;
           }
       }
   }
   int cnt = 0;
   for(int i=2;i<=maxn-5;i++){
       if(!p[i]&&solve(i))
           cnt++;
   }
   cout<<cnt;
}

欧拉筛法

这是这道题时间复杂度最小的优秀解法,时间复杂度只有O(n),但是稍微要复杂一点。其实可以理解为埃氏筛法的进阶版或者优化版。省去了重复筛除：在埃氏筛法中6会被筛去两次(被2和3)。用了一个数组存已经探明了的素数(prime)，用pNum来存当前探明的素数个数。这个算法的核心就是把那些已经探明的素数存放起来，遇到一个新的没有探明的数就拿去，依次看看能不能整除已经探明的那些素数（从2开始）。也就是最最核心的

if(!i%prime[j]) break;

#include "bits/stdc++.h"
using namespace std;
bool solve(int n){
    while(n){
        int temp = n%10;
        if(temp==0||temp==1||temp==4||temp==6||temp==8||temp==9)
            return false;
        n/=10;
    }
    return true;
}
//欧拉筛法
const int MAXN = 20210610;
int prime[MAXN],pNum=0;
bool p[MAXN]={false};
int main()
{
    for(int i = 2;i<=MAXN-5;i++){
        if(!p[i]) prime[pNum++] = i;
        for(int j =0;j<pNum;j++){  //16 2 3 
            if(i*prime[j]>MAXN-5)
                break;
            p[i*prime[j]] = true;
            if(!i%prime[j]) break;//保证某个数只能由最小的质数得到
        }
    }
    int cnt=0;
    for(int i=0;i<pNum;i++){
        if(solve(prime[i]))
            cnt++;
    }
    cout<<cnt;
}
2 4

3 6 9

4 8 //没有12 12只能由2得到

5 10 15 25

6 12

公约数


int gcd(int m, int n)
{
    if (m == 0 || n = = 0)
        return 0;
    if (m % n == 0)
        return n; //如果 b 能被 a 整除则 b 就是最大公约数
    else
        gcd(n, m % n); //递归调用