Java 中数组中最大和最小素数之间的差异

javaobject oriented programmingprogramming更新于 2026/1/4 15:08:17

问题陈述

给定一个整数数组，其中所有元素都小于 1000000。找出数组中最大和最小素数之间的差异。

示例

数组:[ 1, 2, 3, 4, 5 ]

最大素数 = 5
最小素数 = 2

差异 = 5 - 3 = 2。

解决方案

使用埃拉托斯特尼筛法，这是一种找出所有小于给定数字的素数的有效方法。然后我们将找出最大和最小的素数以获得所需的差值。

示例

以下是 Java 中查找所需输出的程序。

public class JavaTester {

   static int MAX = 1000000;
   static boolean prime[] = new boolean[MAX + 1];

   public static void runSieveOfEratosthenes(){
      //reset prime flags to be true
      for(int i=0; i< MAX+1; i++) prime[i] = true;
      //将 1 设置为非素数
      prime[1] = false;

      for (int p = 2; p * p <= MAX; p++) {
         // 如果 prime[p] 未被修改，则它为素数
         if (prime[p]) {
            // 更新 p 的所有倍数
            for (int i = p * 2; i <= MAX; i += p) prime[i] = false;
         }
      }
   }

   public static int difference(int arr[]){
      int min = MAX + 2;
      int max = -1;
      for (int i = 0; i < arr.length; i++) {
         // 检查数字是否为素数
         if (prime[arr[i]] == true) {
            // 设置最大值和最小值
            if (arr[i] > max) max = arr[i];
            if (arr[i] < min) min = arr[i];
         }
      }
      return max - min;
   }

   public static void main(String args[]){
      // 运行筛选
      runSieveOfEratosthenes();
      int arr[] = { 1, 2, 3, 4, 5 };
      System.out.println(difference(arr));
   }
}