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

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

方法一

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

空间复杂度。O(1)

算法

• 第1步 – 声明数字N的类型为int32

• 第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到外循环的当前索引的一半值。在这个循环中，我们将外循环的索引与内循环的索引进行比对，如果是0，那么我们将isPrime设置为false，并打破内循环。

• if isPrime {} – 一旦上述循环结束，我们将检查isPrime的值，如果它是真的，我们将打印这个数字。

输出

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

方法二

在这个方法中，我们将讨论Sieve Eratosthenes算法来寻找1到N之间的质数。这个方法比之前的方法更有效。

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

空间复杂度。O(N)

算法

• 第1步 – 声明数字N的类型为int32

• 第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循环。

  • for j := i * i; j <= N; j = j + i {} – 这个循环从上层循环索引的平方开始运行，直到N，并将内层循环索引增加i，并将primArray从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之间的素数的两种方法。