素数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 <= 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 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] = list.get(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; }

首先判断输入的n是否小于2，如果n小于2，则返回一个长度为0的素数数组。然后定义一个整型数组primes和一个索引idx，用来存放素数和标记素数数组的索引。接着定义一个boolean数组isComposite，用来记录每个数是否为合数，初始时所有数都被标记为非合数。从2开始循环到n，如果当前数为素数，则将它添加到素数数组primes中，并枚举它的倍数，将它们标记为合数。枚举时采用break跳出循环，水平有限的人听这样的字眼总给人

这篇技术文档很不专业的感觉。欧拉筛法的复杂度为O(n)。

三、运行结果验证

为了验证以上代码的正确性，下面给出两组测试数据：

数据一（n=100）：

暴力枚举法：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 埃氏筛法：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 欧拉筛法：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

数据二（n=1000）：

暴力枚举法：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751

757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 埃氏筛法：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 欧拉筛法：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467

479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

从数据可以看出，三种算法得出的素数序列完全一致，证明各算法的正确性。

四、总结

素数是一种重要的数学概念，在计算机编程中也经常碰到。本文从Java语言的角度出发，介绍了素数判断的两种方法：暴力枚举法和筛法。暴力枚举法简单方便，但在n较大时效率低下；筛法则更为高效，尤其是欧拉筛法，能够在O(n log log n)时间内得到素数序列。读者可以根据自己的需求选择适合的方法。