如何在Go语言中显示1到N之间的所有质数？

在本教程中，我们将学习如何打印1到N之间的质数，其中N的值将作为用户输入。简要介绍一下质数：质数只能被1或自身整除。在本教程中，我们将讨论两种方法，一种时间复杂度为O(N^2)，另一种时间复杂度为O(N*log(logN))。

方法一

时间复杂度：O(N^2)

空间复杂度：O(1)

算法

• 步骤1 - 声明int32类型的数字N

• 步骤2 - 从用户处获取输入，这将告诉我们在哪个范围内查找质数。

• 步骤3 - 现在我们调用一个函数，该函数包含查找质数并打印它们的逻辑。

示例1

package main

// fmt package provides the function to print anything
import "fmt"

func printPrimeNumbersBeforeN(N int) {
   // running the for loop from 1 to N
   for i := 2; i <= N; i++ {

      // flag which will confirm that the number is Prime or not
      isPrime := true
      
   // This for loop is checking that the current number have
   // any divisible other than 1
   for j := 2; j <= i/2; j++ {
      if i%j == 0 {
         isPrime = false
         break
      }
   }
   // if the value of the flag is false then the number is not prime
   // and we are not printing it.
   if isPrime {
         fmt.Println(i)
      }
   }
}
func main() {
   // declaring the variable N till which we have to find the Prime Numbers
   var N int
   fmt.Println("Enter the value of N.")  
   // Taking the input of N from the user
   fmt.Scanln(&N)   
   fmt.Println("The prime numbers between 1 to", N, "where N is included are  -")
   
   // calling the function to find and print the prime numbers printPrimeNumbersBeforeN(N)
}

• printPrimeNumbersBeforeN(N) - 这是在Go语言中调用的函数，其中N作为参数传递。在这个定义在main函数之前的函数中，包含了查找质数的核心逻辑。

• func printPrimeNumbersBeforeN(N int) - 这是一个函数定义，它有一个整数作为参数。

• for i := 2; i <= N; i++ {} - 此循环从2运行到N，对于每个数字，我们将在嵌套循环中检查它是否为质数。

• for j := 2; j <= i/2; j++ {} - 如果我们观察到一个数字不是质数，那么它的一个因子将是其值的一半。因此，此循环从2运行到外循环当前索引值的一半。在循环内部，我们对内循环索引进行外循环索引的模运算，如果结果为零，则我们将isPrime设置为false并中断内循环。

• if isPrime {} - 上述循环结束后，我们检查isPrime的值，如果为true，则打印该数字。

输出

Enter the value of N.
25
The prime numbers between 1 to 25 where N is included are -
2
3
5
7
11
13
17
19
23

方法二

在这个方法中，我们将讨论埃拉托色尼筛法来查找1到N之间的质数。这种方法比前面一种方法更有效。

时间复杂度：O(N*log(logN))

空间复杂度：O(N)

算法

• 步骤1 - 声明int32类型的数字N

• 步骤2 - 从用户处获取输入，这将告诉我们在哪个范围内查找质数。

• 步骤3 - 现在我们调用一个函数，该函数包含查找质数并打印它们的逻辑。

示例2

package main

// fmt package provides the function to print anything
import "fmt"

func initializeArray(primeArray []bool, N int) {
   // initializing the array with true
   for i := 0; i < N; i++ {
      primeArray[i] = true
   }
}
func printPrimeNumbersBeforeN(N int) {
   primeArray := make([]bool, N+1)
   initializeArray(primeArray, N+1)
   
   // running the for loop from 1 to under root N
      for i := 2; i*i <= N; i++ {
         if primeArray[i] {

            // This for loop is running from the square of upper
            // loop index until N and traversing over the multiple of i
            // by increasing the j index by i
            for j := i * i; j <= N; j = j + i {
               primeArray[j] = false
            }
         }
      }

      // printing the prime number by checking the status of primeArray status
      for i := 2; i <= N; i++ {
         if primeArray[i] {
            fmt.Println(i)
         }
      }
   }
   func main() {
      //declaring the variable N till which we have to find the Prime Numbers 
      var N int
    
      fmt.Println("Enter the value of N.")

   // Taking the input of N from the user
   fmt.Scanln(&N)
   fmt.Println("The prime numbers between 1 to", N, "where N is include are -")

   // calling the function to find and print the prime numbers
   printPrimeNumbersBeforeN(N)
}

• printPrimeNumbersBeforeN(N) - 这是在Go语言中调用的函数，其中N作为参数传递。在这个定义在main函数之前的函数中，包含了查找质数的核心逻辑。

• func printPrimeNumbersBeforeN(N int) - 这是一个函数定义，它有一个整数作为参数。

• primeArray := make([]bool, N+1) - 在这里，我们创建一个名为**primeArray**的布尔数组，大小为N + 1。

• finitializeArray(primeArray, N+1) - 这行代码调用一个在上面实现的函数，该函数用true初始化数组。

• for i := 2; i*i <= N; i++ {} - 因为任何数字的因子都将出现在该数字的平方根之前，所以我们将for循环从2运行到N的平方根。

• for j := i * i; j <= N; j = j + i {} - 此循环从外循环索引的平方运行到N，并将内循环索引增加i，并将primeArray从true更改为false，因为当前索引已经是某个数字的倍数，所以它不能是质数。

• 最后，我们通过检查**primeArray**来打印质数。

输出

Enter the value of N.
35
The prime numbers between 1 to 35 where N is included are -
2
3
5
7
11
13
17
19
23
29

以上是在Go语言中查找1到N之间质数的两种方法。要了解更多关于Go语言的信息，您可以浏览此教程。

Aman Sharma

更新于：2022年8月26日

2K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习