Java中如何实现找质数的方法？ |21xrx.com

Java中如何实现找质数的方法？

2023-06-16 12:40:03 深夜i -- --

Java 质数算法实现方法

在Java编程中，经常需要找出一定范围内的质数。质数是指除了1和本身之外，不能被其他数整除的数。本文将介绍Java中实现找质数的方法，同时介绍一些实用技巧。

一、暴力解法

最常见的找质数的方法就是暴力解法。该方法就是对于范围内每个数都进行判断，以此排除非质数。具体实现方法如下：


public static boolean isPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0) return false;
  }
  return true;
}

该函数接受一个整数n作为参数，如果n是质数，则返回true，否则返回false。该函数的时间复杂度为O(n√n)，虽然效率不高，但对于一些小数据范围的问题，可以快速得出答案。

二、Eratosthense筛法

Eratosthense筛法是一种经典的找质数算法，其核心思想是除去所有质数的倍数，剩下的数就是质数。具体实现方法如下：


public static boolean[] sieveOfEratosthense(int n) {
  // 初始化数组，全部设置为true
  boolean[] primes = new boolean[n + 1];
  for (int i = 2; i <= n; i++) {
    primes[i] = true;
  }
  // 循环遍历，除去所有质数的倍数
  for (int i = 2; i * i <= n; i++) {
    if (primes[i]) {
      for (int j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }
  return primes;
}

该函数接受一个整数n作为参数，返回一个长度为n+1的布尔数组，其中，primes[i]为true表示i是质数，为false表示i是合数。该函数的时间复杂度为O(nloglogn)，在数据量较大的情况下能够快速得到结果。

三、转化为质因数的乘积

在Java中，可以将质数分解为质因数的乘积，进一步实现找质数的操作。该方法的核心思想是：对于一个数n，如果存在一个质数p，满足p^2<=n且n%p==0，那么n/p一定是质数。具体实现方法如下：


public static boolean isPrime(int n) {
  if (n == 2 || n == 3) return true;
  if (n == 1 || n % 2 == 0) return false;
  int sqrt_n = (int) Math.sqrt(n);
  for (int i = 3; i <= sqrt_n; i += 2) {
    if (n % i == 0) return false;
  }
  return true;
}

该函数接受一个整数n作为参数，如果n是质数，则返回true，否则返回false。该函数的时间复杂度为O(sqrt(n))，在数据范围较小时能够快速得到答案。

本文介绍了三种不同的Java中找质数的方法，对于不同的数据范围，可以采用不同的方法得到答案。

上一篇: idea打包java可执行jar包

下一篇: 能否在手机上运行Java程序

评论区

()

相似文章