2024年4月15日发(作者：)
素数java代码
素数是指只能被1和自己整除的正整数，像2、3、
5、7、11等都是素数。在计算机编程中，判断一个数是否
为素数是一项基本的算法。本文将从Java语言的角度入
手，介绍如何编写素数判断的代码，包括两种方法：暴力
枚举法和筛法。
一、暴力枚举法
暴力枚举法是一种较为简单粗暴的方法，通过一个循
环枚举所有可能的因子，判断是否能被整除。其Java代码
如下：
public static boolean isPrime(int n) { if
(n < 2) { //小于2的数均不是素数 return
false; } for (int i = 2; i <= (n);
i++) { if (n % i == 0) { //能被整除，即不是
素数 return false; } }
return true; //不被整除，即是素数 }
首先判断输入的数n是否小于2，如果n小于2，则直
接返回false，因为小于2的数均不是素数。然后从2开始
循环到n的平方根，检查是否能被整除，如果能则返回
false，否则继续循环，最后返回true表示是素数。
这种方法的时间复杂度为O(√n)，因为最多需要枚举
n的平方根次数。在较小的n值的情况下，这种方法较为有
效，但当n较大时，效率低下。
二、筛法
筛法是用于快速筛选素数的一种高效算法，它的原理
是从小到大依次枚举素数，将其倍数标记为合数。例如，
当枚举到2时，将4、6、8、10等标记为合数；当枚举到3
时，将6、9、12等标记为合数。由于合数被标记多次，所
以这种方法比暴力枚举法更快。
筛法主要有两种：埃氏筛法和欧拉筛法。下面分别介
绍它们的Java代码实现。
2.1 埃氏筛法
埃氏筛法是一种简单直接的筛法，其Java代码如下：
public static int[] getPrimes(int n) { if
(n < 2) { //小于2的数没有素数 return new
int[0]; } boolean[] isPrime = new boolean[n
+ 1]; //初始化所有数为素数 for (int i = 2; i <=
n; i++) { isPrime[i] = true; } for
(int i = 2; i <= (n); i++) { if
(isPrime[i]) { //当前数为素数 for (int
j = i * i; j <= n; j += i) { //枚举它的倍数
isPrime[j] = false; //标记为合
发布者：admin，转转请注明出处：http://www.yc00.com/news/1713129589a2188690.html
评论列表（0条）