素数java代码
素数是指只能被1和自己整除的正整数，像2、3、5、7、11等都是素数。在计算机编程中，判断一个数是否为素数是一项基本的算法。本文将从Java语言的角度入手，介绍如何编写素数判断的代码，包括两种方法：暴力枚举法和筛法。java爱心代码编程简单
一、暴力枚举法
暴力枚举法是一种较为简单粗暴的方法，通过一个循环枚举所有可能的因子，判断是否能被整除。其Java代码如下：
public static boolean isPrime(int n) {    if (n < 2) { //小于2的数均不是素数        return false;    }    for (int i = 2; i <= Math.sqrt(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 <= Math.sqrt(n); i++) {        if (isPrime[
i]) { //当前数为素数            for (int j = i * i; j <= n; j += i) { //枚举它的倍数                isPrime[j] = false; //标记为合数            }        }    }    List<Integer> list = new ArrayList<>();    for (int i = 2; i <= n; i++) {        if (isPrime[i]) { //将素数添加到列表中            list.add(i);        }    }    int[] primes = new int[list.size()]; //将列表转成数组    for (int i = 0; i < primes.length; i++) {        primes[i] = (i);    }    return primes; }
首先判断输入的n是否小于2，如果n小于2，则返回一个长度为0的素数数组。然后初始化一个boolean数组isPrime，用来记录每个数是否为素数，初始时所有数都被标记为素数。接着从2开始循环到n的平方根，判断当前数是否为素数，如果是则枚举它的倍数并将它们标记为合数。最后遍历一遍isPrime数组，将所有素数添加到列表中，再将列表转成数组并返回。
这种方法的时间复杂度为O(n log log n)，由于每个合数只会被标记一次，所以效率非常高。
2.2 欧拉筛法
欧拉筛法是一种更优秀的筛法，它通过每个合数只被它的最小质因数筛选一次来提升效率。其Java代码如下：
public static int[] getPrimes(int n) {    if (n < 2) { //小于2的数没有素数        return new int[0];    }    int[] primes = new int[n + 1]; //存放素数的数组    int idx = 0; //素数数组的索引    boolean[] isComposite = new boolean[n + 1]; //记录合数    for (int i = 2; i <= n; i++) {        if (!isComposite[i]) { //当前数为素数            primes[idx++] = i; //将它添加到素数数组中        }        for (int j = 0; j < idx && primes[j] * i <= n; j++) {            isComposite[primes[j] * i] = true; //标记为合数            if (i % primes[j] == 0) { //跳出循环                break;            }        }    }    int[] res = new int[idx];    System.arraycopy(primes, 0, res, 0, idx); //复制到res数组中并返回    return res; }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。