Java 实现轮篮筛法以在给定范围内生成素数

在给定范围内找到素数的朴素方法是检查每个数字是否是素数。此外，我们需要进行与给定数字相等的迭代次数来检查数字是否是素数。因此，朴素方法非常耗时，我们需要对其进行优化以使其时间高效。

在本教程中，我们将学习由筛子提供的轮篮因式分解和埃拉托斯特尼筛法算法，以高效地找到给定范围内的素数。

问题陈述 − 给定左右整数值。我们需要实现轮篮因式分解和埃拉托斯特尼筛法算法来找到给定范围内的素数。

示例

输入

left = 10;  right = 50;

输出

11 13 17 19 23 29 31 37 41 43 47

解释

It prints the prime numbers between 10 and 50.

输入

left = 9;  right = 10;

输出

“”

说明

It prints an empty string as there is no prime numbers between 9 and 10.

输入

left = 144; right = 200;

输出

149 151 157 163 167 173 179 181 191 193 197 199

方法1

在这个方法中，我们将使用埃拉托色尼筛选法（Sieve of Eratosthenes algorithm）找到两个给定数字之间的质数。

在埃拉托色尼筛选法中，我们使用一个长度为N的数组来存储每个数字是否为质数的布尔值。对于偶数，我们将其标记为false，因为它们不是质数。然后，我们遍历每个未标记的数字，并将其倍数对应的布尔值从true改为false。

步骤

• 第一步 - 定义一个numbers[]数组来存储每个数字是否为质数的布尔值。

• 第二步 - 执行createMatrix()函数，找到1到10,000,000之间的质数，并更新numbers[]数组。

• 第三步 - 从4开始遍历到给定范围。如果索引是偶数，将numbers[p]初始化为false。否则，初始化为true。

• 第四步 - 使用循环从3开始遍历到给定范围。如果numbers[p]为true，则将该数的所有倍数标记为false。

• 第五步 - 执行getPrimes()函数，获取left和right之间的所有质数。

• 第五步.1 - 在getPrimes()函数中，遍历给定范围内的数组，并打印索引值，当数组元素为true时。

示例

import java.io.*;

public class Main {
   // Maximum range
   static boolean numbers[] = new boolean[1000001];
   static void createMatrix() {
      // max range
      int range = 1000000;
      // Initially mark even numbers as non-prime and odd numbers as prime
      for (int p = 4; p <= range; ++p) {
         if (p % 2 == 0)
            numbers[p] = false;
         else
            numbers[p] = true;
      }
      // Traverse all odd numbers and update if the number is not prime
      for (int p = 3; p <= Math.sqrt(range); p += 2) {
         // If the number is prime
         if (numbers[p] == true) {
            // Update all multiples of p as non-prime
            for (int q = p * p; q <= range; q += p) {
               numbers[q] = false;
            }
         }
      }
   }
   static void getPrimes (int left, int right) {
      System.out.println("Prime numbers in the given range are:");
      for (int p = left; p <= right; ++p) {
         // Printing prime numbers in the range
         if (numbers[p] == true) {
            System.out.print(p + " ");
         }
      }
   }
   public static void main(String[] args) {
      int left = 10;
      int right = 50;
      createMatrix();
      // Get prime numbers in the given range
      getPrimes(left, right);
   }
}

输出

Prime numbers in the given range are:
11 13 15 17 19 21 23 27 29 31 33 37 39 41 43 47

时间复杂度 – O(N*logN)，其中O(N)用来遍历数组，O(logN)用来标记所有的倍数为false。

方法2

在这种方法中，我们需要取出素数的基本列表。在这里，我们将使用{2, 3, 5}。然后，我们需要在所有基本列表的素数的乘积后决定轮子的大小。所以，我们的轮子大小将是(235) 30。

在下一步中，我们需要取出从1到轮子大小的所有素数，以制作一个轮子。我们将取出{7, 11, 13, 17, 19, 23, 29, 31}，因为我们已经包含了2, 3和5在基本列表中。

所以，轮子包含30个数字的一层。在每一层中，我们检查该数字是否可被任何较小的整数整除，以确定该数字是否为素数。

步骤

• 第1步 - 初始化’isNumPrime’为true，假设该数字是素数。

• 第2步 - 同样，初始化primes数组为轮子的第一层的素数。

• 第3步 - 如果数字小于2，则将’isNumPrime’更新为false。

• 第4步 - 如果数字可被2、3或5整除，则将’isNumPrime’更新为false。

• 第5步 - 在步骤30中，从0到sqrt(Number)设置循环迭代次数，因为轮子的每一层包含30个数字。

• 第6步 - 使用嵌套循环遍历第一层的所有素数。如果第一层的素数大于sqrt(num)，则打破嵌套循环。

• 第7步 - 否则，如果数字可被第一层的素数+p（30的倍数）整除，则将’isNumPrime’更新为false，并打破嵌套循环。

• 第8步 - 在外循环中，如果’isNumPrime’的值为false，则打破外循环。

• 第9步 - 返回’isNumPrime’变量的值。

示例

在这个示例中，我们遍历给定范围内的每个数字，并使用轮子分解算法来检查它是否是素数。

import java.util.*;

public class Main {
   static boolean checkForPrime(int num) {
      boolean isNumPrime = true;
      // Wheel of prime numbers
      int[] primes = { 7, 11, 13, 17, 19, 23, 29, 31 };
      // Base Case
      if (num < 2) {
         isNumPrime = false;
      }
      if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0) {
         isNumPrime = false;
      }
      // Check in the wheel P is the layer of the wheel
      for (int p = 0; p < Math.sqrt(num); p += 30) {
         // Check for the list of Sieve in primes[]
         for (int pm : primes) {
            // When the prime number exceeds the square root of the num
            if (pm > Math.sqrt(num)) {
               break;
            }
            // If num is multiple of pm in the current wheel
            else {
               if (num % (pm + p) == 0) {
                  isNumPrime = false;
                  break;
               }
            }
            // When a number is non-prime in the current layer
            if (!isNumPrime)
               break;
         }
      }
      return isNumPrime;
   }
   public static void main(String args[]) {
      int left = 10;
      int right = 50;
      System.out.println("Prime numbers in the given range are :");
      for (int p = left; p <= right; ++p) {
         if (checkForPrime(p) == true) {
            System.out.print(p + " ");
         }
      }
   }
}

输出

Prime numbers in the given range are:
11 13 17 19 23 29 31 37 41 43 47

时间复杂度 – O(N * N1/2)

空间复杂度 – O(1)

埃拉托斯特尼筛选法只用于在特定范围内查找质数，而轮筛法用于在大范围内找出所有质数。