当前位置：极客教程 > Go 语言 > Go 实例 > Golang 如何显示从1到N的所有素数

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

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)
}
Go

  • 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
Go

方法二

在这个方法中，我们将讨论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)
}
Go

  • 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
Go

以上是在Golang中寻找1到N之间的素数的两种方法。

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

Go语言 精品教程

登录

找回密码？

注册