Java 练习题：输出纯素数

纯素数简介

所谓纯素数就是该数本身不仅是素数，并且该数的每一位都是素数。
例如：23,37是纯素数，但13,29不是。

任务要求

输出55555内所有的纯素数，按每行20个的格式化输出，最后再输出总个数。

思路解析

按照正常的思路应该是遍历数值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}

源码奉上

package net.army.day01;

import java.util.HashSet;
import java.util.Set;

/**
 * 功能：计算纯素数
 * 作者：梁辰兴
 * 日期：2023年02月28日
 */
public class TestWork {
    public static void main(String[] args) {
        int n = 55555;
        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.print(i + "\t");
                if (count % 20 == 0) {
                    System.out.println();
                }
            }
        }
        System.out.println("纯素数一共：" + count + "个。");
    }
}

运行效果

总结

对素数理解还不够全面，判断方法还需改进。加强平时练习，补充不足知识。

如您有更优方法还望放置评论区供大家学习，致谢。