Java中如何使用boolean二维数组实现埃氏筛法判断素数

实现目标 #

使用boolean二维数组实现埃拉托斯特尼筛法，流程如下：

• 根据用户输入的数值n，创建对应大小的n×n图表矩阵
• 遍历矩阵每个索引位置对应的实际数值，若数值为素数则将对应数组位置标记为true
• 最终输出仅展示素数的图表矩阵，同时统计矩阵总数字量、素数总数量

现有待调试代码 #

public class Runner {
public static void main(String[] args) {
    Scanner sc= new Scanner(System.in);    // 接收用户输入的流对象
    System.out.println("将为你演示埃拉托斯特尼筛法");  
    System.out.println("请输入目标数值：");
    int n= sc.nextInt(); // 用户输入n，将生成n×n大小的矩阵，例：输入5则生成5×5矩阵
    int charting = 0; // 统计矩阵内1到n²的总数字个数
    int prime = 0; // 统计矩阵内的素数总个数
    boolean[][] Chart = new boolean[n+1][n+1]; // 按输入初始化二维数组
    // 嵌套循环遍历二维数组的行和列
    for(int i = 1; i < Chart.length; i++) {
        for(int j = 1; j < Chart[i].length; j++) {
            charting++; // 遍历到每个数组位置时计数累加
            // 待修复的素数判断逻辑
            if(i-1 % i == 0) {
                Chart[i][j] = false;
            }
            else {
                Chart[i][j] = true;
                
            }
            
            }
            
            
        }
    
    System.out.println("矩阵内总数字个数：" + charting);
    System.out.println("筛法处理前的原始矩阵：");
    PrintChartPreCode(n,n);
    System.out.println("矩阵内素数总个数：" + prime); 
}

// 打印矩阵的方法
public static void PrintChartPreCode(int rows, int columns) {
    int x = rows;
    int y = columns;
    for(int i = 0; i < x; i++) { // 遍历行
        for(int j = 0; j < y; j++) { // 遍历列
            System.out.print((j + y*i + 1) + "|"); 
            
        }
        System.out.println();
    }
 }
}

现存代码问题 #

• 素数判断逻辑完全失效：判断条件i-1 % i == 0存在运算符优先级错误，取模运算优先级高于减法，实际等价于判断i - (1%i) == 0，结果恒为假，完全无法区分素数和合数，也没有实现埃氏筛「标记素数所有倍数为合数」的核心逻辑
• 坐标和数值映射错误：判断逻辑仅使用行坐标i，完全未关联列坐标j，无法对矩阵每个位置的对应数值做正确标记
• 统计逻辑缺失：素数计数变量prime定义后从未累加，最终输出结果恒为0
• 打印逻辑未关联标记结果：现有打印方法只能输出原始数字矩阵，无法展示筛法处理后的素数分布
• 缺少必要导入：未导入java.util.Scanner类，代码无法直接编译运行

修复后可运行代码 #

import java.util.Scanner;

public class Runner {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("埃拉托斯特尼筛法演示");
        System.out.println("请输入矩阵大小n：");
        int n = sc.nextInt();
        int totalNum = 0;
        int primeCount = 0;
        boolean[][] isPrime = new boolean[n][n];
        int maxNum = n * n;

        // 埃氏筛核心逻辑：先初始化所有≥2的数为素数，再逐轮标记合数
        boolean[] sieve = new boolean[maxNum + 1];
        for (int k = 2; k <= maxNum; k++) {
            sieve[k] = true;
        }
        for (int k = 2; k * k <= maxNum; k++) {
            if (sieve[k]) {
                for (int multiple = k * k; multiple <= maxNum; multiple += k) {
                    sieve[multiple] = false;
                }
            }
        }

        // 填充二维数组，同步统计总数和素数个数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int currentNum = i * n + j + 1;
                totalNum++;
                isPrime[i][j] = sieve[currentNum];
                if (isPrime[i][j]) {
                    primeCount++;
                }
            }
        }

        System.out.println("矩阵内总数字个数：" + totalNum);
        System.out.println("原始矩阵：");
        printRawChart(n);
        System.out.println("矩阵内素数总个数：" + primeCount);
        System.out.println("筛选后素数矩阵（非素数位置用*替代）：");
        printPrimeChart(isPrime, n);
    }

    // 打印原始数字矩阵
    public static void printRawChart(int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.printf("%-4d|", i * n + j + 1);
            }
            System.out.println();
        }
    }

    // 打印筛选后的素数矩阵
    public static void printPrimeChart(boolean[][] isPrime, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int currentNum = i * n + j + 1;
                if (isPrime[i][j]) {
                    System.out.printf("%-4d|", currentNum);
                } else {
                    System.out.printf("%-4s|", "*");
                }
            }
            System.out.println();
        }
    }
}

修复说明 #

• 补全java.util.Scanner导入语句，解决编译报错
• 单独实现标准埃氏筛逻辑：先将1维筛表中所有≥2的位置初始化为true，从最小素数2开始，把每个素数的所有倍数标记为false（合数），时间复杂度为O(nloglogn)，符合筛法的效率要求
• 统一坐标映射规则：二维矩阵第i行第j列对应的实际数值为i * n + j + 1，和打印逻辑的计算规则保持一致，避免标记错位
• 填充二维数组时同步统计总数字个数、素数个数，保证输出的统计值准确
• 新增素数矩阵专属打印方法，非素数位置用*占位，直观展示筛选结果

内容的提问来源于stack exchange，提问作者Jose Espinoza