可以通过控制台选择模式并按照提示输入数据程序会输出相应结果。javaimport 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; } ListInteger 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 ListInteger 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; } } } ListInteger 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; } }程序说明1. 功能选择运行后输入1进入范围查找模式输入2进入单数判断模式。2. 范围查找模式1使用埃拉托斯特尼筛法快速生成所有不超过N的素数。输出素数个数并按每行10个的格式打印素数。3. 单数判断模式2使用优化的试除法只检查到平方根并跳过偶数判断输入的正整数是否为素数。
素数查找程序
可以通过控制台选择模式并按照提示输入数据程序会输出相应结果。javaimport 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; } ListInteger 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 ListInteger 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; } } } ListInteger 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; } }程序说明1. 功能选择运行后输入1进入范围查找模式输入2进入单数判断模式。2. 范围查找模式1使用埃拉托斯特尼筛法快速生成所有不超过N的素数。输出素数个数并按每行10个的格式打印素数。3. 单数判断模式2使用优化的试除法只检查到平方根并跳过偶数判断输入的正整数是否为素数。
