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

javaobject oriented programmingprogramming更新于 2024/7/30 19:56:17

在给定范围内查找素数的简单方法是检查每个数字是否为素数。此外,我们需要进行与给定数字相等的迭代来检查该数字是否为素数。因此,这种简单的方法非常耗时,我们需要对其进行优化以使其节省时间。

在本教程中,我们将学习 Sieve 提供的轮分解和埃拉托斯特尼筛法算法,以有效地查找给定范围内的素数。

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

示例

输入

left = 10; right = 50;

输出

11 13 17 19 23 29 31 37 41 43 47

解释

它打印 10 到 50 之间的素数。

输入

left = 9; right = 10;

输出

""

解释

由于 9 和 10 之间没有素数,因此会打印一个空字符串。

输入

left = 144; right = 200;

输出

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

方法 1

在此方法中,我们将使用埃拉托斯特尼筛法算法在两个给定数字之间查找素数。

在埃拉托斯特尼筛法算法中,我们使用长度为 N 的数组根据数字是否为素数来存储布尔值。对于偶数,我们存储 false,因为它们是非素数。之后,我们访问每个未标记的数字,并将其倍数的布尔值从 true 更改为 false。

算法

  • 步骤 1 - 根据数字是否为素数,定义 numbers[] 数组以存储布尔值。

  • 步骤 2 - 执行 createMatrix() 函数以查找 1 到 10,000,000 之间的素数并更新 numbers[] 数组。

  • 步骤 3 - 从 4 开始遍历到给定的范围。如果索引为偶数,则用 false 初始化 numbers[p]。否则,用 true。

  • 步骤 4 - 使用循环从 3 到给定的范围进行迭代。如果数字 [p] 为真,则将该数字的所有倍数标记为假。

  • 步骤 5 - 执行 getPrimes() 函数以获取左右之间的所有素数。

  • 步骤 5.1 - 在 getPrimes() 函数中,遍历给定范围内的数组,如果数组元素为真,则打印索引值。

示例

import java.io.*;

public class Main {
   // 最大范围
   static boolean numbers[] = new boolean[1000001];
   static void createMatrix() {
      // max range
      int range = 1000000;
      // 最初将偶数标记为非质数,将奇数标记为质数
      for (int p = 4; p <= range; ++p) {
         if (p % 2 == 0)
            numbers[p] = false;
         else
            numbers[p] = true;
      }
      // 遍历所有奇数,如果数字不是素数,则更新
      for (int p = 3; p <= Math.sqrt(range); p += 2) {
         // 如果数字是质数
         if (numbers[p] == true) {
            // 将 p 的所有倍数更新为非素数
            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) {
         // 打印范围内的素数
         if (numbers[p] == true) {
            System.out.print(p + " ");
         }
      }
   }
   public static void main(String[] args) {
      int left = 10;
      int right = 50;
      createMatrix();
      // 获取给定范围内的素数
      getPrimes(left, right);
   }
}

输出

给定范围内的素数为:
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}。之后,我们需要在将基本列表中的所有素数相乘后确定轮子大小。因此,我们的轮子大小将是 ( 2*3*5 ) 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 - 使用循环进行从 0 到 1 的迭代sqrt(Number) 在第 30 步,因为轮盘的每一层包含 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;
      // 素数轮
      int[] primes = { 7, 11, 13, 17, 19, 23, 29, 31 };
      // 基本情况
      if (num < 2) {
         isNumPrime = false;
      }
      if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0) {
         isNumPrime = false;
      }
      // 检查轮子 P 是轮子的层数
      for (int p = 0; p < Math.sqrt(num); p += 30) {
         // 检查 primes[] 中的 Sieve 列表
         for (int pm : primes) {
            // 当素数超过数字的平方根时
            if (pm > Math.sqrt(num)) {
               break;
            }
            // 如果 num 是当前轮子中 pm 的倍数
            else {
               if (num % (pm + p) == 0) {
                  isNumPrime = false;
                  break;
               }
            }
            // 当当前层中的数字非素数时
            if (!isNumPrime)
               break;
         }
      }
      return isNumPrime;
   }
   public static void main(String args[]) {
      int left = 10;
      int right = 50;
      System.out.println("给定范围内的素数有 :");
      for (int p = left; p <= right; ++p) {
         if (checkForPrime(p) == true) {
            System.out.print(p + " ");
         }
      }
   }
}

输出

给定范围内的素数有:
11 13 17 19 23 29 31 37 41 43 47

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

空间复杂度 – O(1)

只有当我们需要在特定范围内找到素数时,才会使用埃拉托斯特尼筛法算法,但轮子分解算法用于查找大范围内的所有素数。


相关文章


有用资源