Haskell 程式用於顯示 1 到 n 之間的所有素數

本教程將討論編寫一個程式，以在 Haskell 程式語言中顯示從 1 到 N 的所有素數。Haskell 是一種宣告式、強型別和函式式語言。Haskell 中的計算是數學函式。

素數必須有兩個正因子：1 和它本身。

示例 2,3,5,7,..

注意 1 不是素數，因為它只有一個因子。

演算法步驟

  • 實現一個函式來檢查一個數是否為素數。

  • 實現一個函式來生成一個範圍內所有素數。

  • 顯示素數。

  • 程式：顯示 1 到 N 之間的所有素數

  • 我們將程式分解成更簡單的函式。

語法

函式：查詢一個數的所有因子。

–- function declaration
factors :: Int->[Int]
–- function definition
factors n = [x | x<-[1..n], (mod n x)==0]

上述函式是一個實用函式，用於檢查一個數是否為素數。我們聲明瞭一個名為 factor 的函式，它接受一個整數作為輸入並返回一個整數列表。在函式中，我們使用列表推導式生成從 1 到 n（引數）的數字，並返回能整除引數 n 的數字，即列表推導式生成引數 n 的所有因子並將其作為列表返回。

Ex: output for factors 50 is:
[1,2,5,10,25,50]
Function to check a number is prime
-- function declaration
isPrime :: Int->Bool
-- function definition
isPrime n = (factors n) == [1,n]

上述函式是一個實用函式，用於在給定範圍內生成素數。我們聲明瞭一個名為 isPrime 的函式，它接受一個整數作為輸入並返回一個布林值。在函式定義中，我們使用引數作為第一個引數呼叫 factors 函式，並將返回的列表與包含兩個數字（1 和引數）的列表進行比較，即此函式檢查一個數的因子是否等於 1 和該數本身，這是素數的定義，如果該數是素數則返回真，否則返回假。

Ex: Output for isPrime 13 is:
True

函式：以迭代方式生成 1 到 N 的素數

-- function declaration
generatePrime :: Int->[Int]
-- function definition
generatePrime n = [x | x<-[1..n], isPrime x]

上述函式生成 1 到 N 的所有素數。我們聲明瞭一個名為 generatePrime 的函式，它接受一個整數作為引數並返回一個整數列表。在函式定義中，我們使用列表推導式生成從 1 到 n 的整數列表，並使用 isPrime 函式對其進行過濾，該函式僅返回為素數的數字。

Ex: output for generatePrime 50 is:
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

函式：以遞迴方式生成 1 到 N 的素數

-- function declaration
generatePrime2 :: Int->[Int]
-- function definition

-- base case
generatePrime2 0 = []

generatePrime2 n = if (isPrime n)
then generatePrime2 (n-1) ++ [n]
else generatePrime2 (n-1)

上述函式 generatePrime2 以遞迴方式生成 1 到 N 的所有素數。我們聲明瞭該函式，它接受一個整數作為輸入並返回一個整數列表。在函式定義中，我們接受一個整數 n 作為引數，並檢查它是否為素數。如果 n 是素數，我們將 n 與使用引數 n-1 進行遞迴呼叫的結果連線起來。如果 n 不是素數，我們將返回使用引數 n-1 進行遞迴呼叫。這將持續進行，直到達到基本情況，即當 n 達到 0 時，函式返回一個空列表。這以遞迴方式檢查從 n 到 0 的素數。

Example: Output for generatePrime 60 is:
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]

整體程式

factors :: Int->[Int]
factors n = [x | x<-[1..n], (mod n x)==0]

isPrime :: Int->Bool
isPrime n = (factors n) == [1,n]

generatePrime :: Int->[Int]
generatePrime n = [x | x<-[1..n], isPrime x]

main = do
   let n = 100
   print (generatePrime n)

輸出

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

在上述程式中，我們組合了所有實用函式以在給定範圍內生成素數。在主函式中，我們宣告並初始化了數字 n 的值為 100，並呼叫了 generatePrime 函式，該函式生成從 1 到 N 的所有素數。最後，我們列印了被呼叫函式返回的列表。

結論

在本教程中，我們討論了編寫一個程式以在 Haskekell 程式語言中顯示從 1 到 N 的所有素數。

更新於： 2022年10月27日

2K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告