一起创业网-为互联网创业者服务

怎么求素数java程序

在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求素数