题目来源： 第十二届蓝桥杯国赛Java B组试题

题目解析

此题按照正常的思路应该是遍历数值n，找到n所有的素数然后在对的出来的所有素数各个数字进行判断，属于2,3,5,7即可。

但此题给的n=20210605，一个八位的数字，如果单纯按照上面的思路进行实现，计算时间将会变得非常漫长。

这里我们可以使用埃氏筛法，快速找出n中所有的素数，然后在找出来的素数中找出纯素数即可。

什么是埃氏筛法？

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

如：n=10，则有数组：

• {1，2，3，4，5，6，7，8，9，10}

因为1不是素数，所以给1加上删除标记：

• { 1 ，2，3，4，5，6，7，8，9，10}

从2开始遍历：

• { 1 ，2
  ，3，4，5，6，7，8，9，10}

然后将后面可以被2整除的数都加上删除标记，如4，6，8，10都是可以被2整除的，所以需要加上删除标记：

• { 1 ，2
  ，3，4，5，6，7，8，9，10}

接着遍历3：

• { 1 ，2，3，4，5，6，7，8，9，10}

由于6和9都是可以被3整除的，因此也需要加上删除标记：

• { 1 ，2，3，4，5，6，7，8，9，10}

此时我们就已经得出了10内的所有素数~！

• {2，3，5，7}

接下来我们只需要运用这个思路到具体的代码中即可~！！

具体代码

import java.util.*;


public class Main {
  public static void main(String[] args) {
    int n = 20210605;
    int count = 0;
    int[] vs = new int[n+1];
    Set<Integer> set = new HashSet<>();
    
    for(int i = 2; i <= n; i++) {
      if (vs[i] == 0) {
        set.add(i);
        for(int j = i+i; j <= n; j += i) {
          vs[j] = -1;
        }
      }
    }
    
    for(int i : set) {
      char[] chars = String.valueOf(i).toCharArray();
      boolean flag = true;
      for(char c : chars) {
        if (!(c == '2' || c == '3' || c == '5' || c == '7')) {
          flag = false;
          break;
        }
      }
      if (flag) {
        ++count;
      }
    }
    System.out.println(count);
    }
}

运行结果

1903

若上述代码存在任何的问题，或者您有更优解，欢迎在下方评论区提出~！