在Java中求素数的方法有多种,下面我将介绍几种常见的方法,并提供相应的代码示例。
方法一:试除法
试除法是最基本的判断素数的方法,通过从2开始逐个尝试将待判断的数除以从2到该数的平方根的所有自然数,如果存在能整除该数的自然数,则该数不是素数;否则,该数是素数。这种方法的时间复杂度为O(sqrt(n))。
```java
public class PrimeNumber {
public static boolean isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int num = 17;
if (isPrime(num)) {
System.out.println(num + "是素数");
} else {
System.out.println(num + "不是素数");
}
}
}
```
方法二:埃氏筛法
埃氏筛法是一种简单直观的素数筛法,用来查找一定范围内的素数。其基本思想是:从2开始,将每个素数的倍数都标记成合数,一直到目标范围内所有的素数都被筛选出来为止。具体实现方法是使用一个boolean类型的数组,标记索引对应的数字是否为素数。
```java
public class PrimeSieve {
public static void main(String[] args) {
int n = 100;
boolean[] isPrime = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
isPrime[i] = true;
}
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
System.out.print(i + " ");
}
}
}
}
```
方法三:优化后的试除法
为了提高效率,可以在试除法中跳过偶数(除了2),因为除了2以外的偶数都不是素数。
```java
public class OptimizedPrime {
public static boolean isPrime(int num) {
if (num < 2) {
return false;
}
if (num == 2) {
return true;
}
if (num % 2 == 0) {
return false;
}
for (int i = 3; i <= Math.sqrt(num); i += 2) {
if (num % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int num = 17;
if (isPrime(num)) {
System.out.println(num + "是素数");
} else {
System.out.println(num + "不是素数");
}
}
}
```
方法四:输入输出
可以编写一个程序,让用户输入一个整数m,然后输出小于m的所有素数。
```java
import java.util.Scanner;
public class SearchPrime {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
for (int i = 2; i < m; i++) {
if (isPrime(i)) {
System.out.println(i);
}
}
sc.close();
}
public static boolean isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}
```
以上是几种常见的Java求素数