当前位置：首页 > news >正文

素数查找程序

news 2026/6/13 12:11:10

可以通过控制台选择模式，并按照提示输入数据，程序会输出相应结果。

java

import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * 素数查找程序 * 功能：1. 输出 2 到 N 之间的所有素数 * 2. 判断一个正整数是否为素数 */ public class PrimeFinder { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("======= 素数查找器 ======="); System.out.println("请选择功能："); System.out.println("1. 查找指定范围内的所有素数"); System.out.println("2. 判断一个数是否为素数"); System.out.print("请输入选项 (1 或 2): "); int choice; try { choice = scanner.nextInt(); } catch (Exception e) { System.out.println("输入无效，请输入数字 1 或 2。"); scanner.close(); return; } switch (choice) { case 1: findPrimesInRange(scanner); break; case 2: checkPrimeNumber(scanner); break; default: System.out.println("无效选项，请重新运行程序并输入 1 或 2。"); } scanner.close(); } /** * 模式1：查找并输出 [2, max] 内的所有素数 */ private static void findPrimesInRange(Scanner scanner) { System.out.print("请输入正整数上限 N (N >= 2): "); int N; try { N = scanner.nextInt(); if (N < 2) { System.out.println("上限不能小于 2，没有素数可输出。"); return; } } catch (Exception e) { System.out.println("输入无效，请输入正整数。"); return; } List<Integer> primes = sieveOfEratosthenes(N); System.out.println("2 到 " + N + " 之间的素数共有 " + primes.size() + " 个："); // 每行输出 10 个素数，格式化显示 int count = 0; for (int prime : primes) { System.out.printf("%-5d", prime); count++; if (count % 10 == 0) { System.out.println(); } } System.out.println(); // 换行 } /** * 模式2：判断一个正整数是否为素数 */ private static void checkPrimeNumber(Scanner scanner) { System.out.print("请输入要判断的正整数: "); int num; try { num = scanner.nextInt(); if (num < 2) { System.out.println(num + " 不是素数（素数定义要求大于1）。"); return; } } catch (Exception e) { System.out.println("输入无效，请输入正整数。"); return; } boolean isPrime = isPrimeOptimized(num); if (isPrime) { System.out.println(num + " 是素数。"); } else { System.out.println(num + " 不是素数。"); } } /** * 埃拉托斯特尼筛法：返回 [2, max] 内所有素数 * 时间复杂度 O(n log log n)，空间复杂度 O(n) */ private static List<Integer> sieveOfEratosthenes(int max) { boolean[] isPrime = new boolean[max + 1]; // 初始化，假设 2..max 都是素数 for (int i = 2; i <= max; i++) { isPrime[i] = true; } for (int i = 2; i * i <= max; i++) { if (isPrime[i]) { // 从 i*i 开始标记，因为更小的倍数已被处理 for (int j = i * i; j <= max; j += i) { isPrime[j] = false; } } } List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= max; i++) { if (isPrime[i]) { primes.add(i); } } return primes; } /** * 优化的试除法判断素数： * - 单独处理 2 和偶数 * - 只需检查到 sqrt(n) 的奇数因子 */ private static boolean isPrimeOptimized(int n) { if (n < 2) return false; if (n == 2) return true; if (n % 2 == 0) return false; int limit = (int) Math.sqrt(n); for (int i = 3; i <= limit; i += 2) { if (n % i == 0) { return false; } } return true; } }