Golang 如何显示从1到N的所有质数

在本教程中，我们将学习如何打印从1到N的质数，其中N的值将作为用户输入。关于质数的简短介绍是，质数是只能被1或本身整除的数。在本教程中，我们将讨论两种方法，一种将花费O(N^2)的时间，另一种将花费O(N*log(logN))的时间。

方法1

时间复杂度：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) – 这是在Golang中调用的函数，其中N作为参数传入。在这个函数中，即在主函数之前定义的函数，找到素数的核心逻辑。

• 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

方法2

在这个方法中，我们将讨论筛选埃拉托色尼斯算法，以找到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) – 这是在Golang中调用的函数，其中N作为参数传递。在这个函数中，上面定义的主函数之前，找到素数的核心逻辑存在。

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

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

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

  • for i := 2; i*i <= N; i++ {} – 由于任何数的因子都会出现在该数的平方根之前，所以我们从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

这是在Golang中找到1到N之间的素数的上述两种方法。 要了解更多关于Golang的信息，您可以查看 this 教程。