國立臺南大學資訊工程學系

資工三「演算法」課程
第一次作業

題目: Primality Testing

班級 ： 資工三
姓名 ： 林哲維
學號 ： S11159025

老師：陳宗禧

中華民國 113 年 10 月 07 日
 目錄
(一) 簡 介 及 問 題 描 述 … … … .……………..…………………………………………1
1. 簡 介 … … … … … .…………………………………………………………………………2
2. 問 題 … … … … … … … … … … .……………………………………………………………4
(二) 理 論 分 析 … .………………………..………………………………………8
(三) 演 算 法 則 … .…………………………..……………………………………10
(四) 程 式 設 計 環 境 架 構 .………………………..…………………………………12
(五) 程 式 .…………………………………………..………………………………14
(六) 執 行 結 果 、 討 論 與 心 得 .………………………..……………………………18

參考文獻………………………………………………………….…………………22

-2-
(一) 簡介及問題描述
設計與實作三種質數測試 (Primality test)演算法，理論驗證與實驗分析該問題!

1. 簡介

求 Prime(n)? 首先定義 一整數 n，判斷 n 是質數 or 合成數? …

質數是指大於 1 的自然數，且只能被 1 和自身整除的數字。合成數則是大於 1 的自然數，但有其他的整除因子。質數在數學和計算機科學中具

有重要的地位，特別是在密碼學和數論中。質數的分布和特性吸引了許多數學家進行深入研究。

對於一個整數 n，質數測試的目的是確定𝑛是否為質數。這個問題可以通過不同的算法進行解決，這些算法各自有不同的計算複雜度和準確性。
以下將介紹四種常見的質數測試算法，並對其進行理論驗證與實驗分析。

2. 問題

Prime(n)問題定義：

求 Prime(n)，實作與分析
i. Basic Prime Testing
ii. Fermat Primality Testing
iii. Miller-Rabin Primality Testing
iv. Sieve of Eratosthenes
v. Mersenne Prime Number discovery 2m-1

-3-
(二) 理論分析
1. Basic Prime Testing 理論
This is an approach that goes in a way to convert definition of prime numbers
to code. It checks if any of the number less than a given number(N) divides the
number or not. But on observing the factors of any number, this method can be
limited to check only till √N. This is because, product of any two numbers
greater than √N can never be equal to N
2. Fermat Primality Testing 理論
(1) Repeat following k times:
(a) Pick a randomly in the range [2, n - 2]
(b) If gcd(a, n) ? 1, then return false
(c) If an-1 ≢ 1 (mod n), then return false
(2) Return true [probably prime].
3. Miller-Rabin Primality Testing 理論
bool isPrime(int n, int k)
(1) Handle base cases for n < 3
(2) If n is even, return false.
(3) Find an odd number d such that n-1 can be written as d*2r.
Note that since n is odd, (n-1) must be even and r must be
greater than 0.
(4) Do following k times
if (millerTest(n, d) == false)
return false
(5) Return true.
This function is called for all k trials. It returns false if n is composite and
returns true if n is probably prime. d is an odd number such that d*2r = n-1 for
some r>=1

bool millerTest(int n, int d)

(1) Pick a random number 'a' in range [2, n-2]
(2) Compute: x = pow(a, d) % n
(3) If x == 1 or x == n-1, return true.
Below loop mainly runs 'r-1' times.
(4) Do following while d doesn't become n-1.
(a) x = (x*x) % n.
(b) If (x == 1) return false.
(c) If (x == n-1) return true.
4. Sieve of Eratosthenes 理論

-4-
The sieve of Eratosthenes is one of the most efficient ways to find all primes
smaller than n when n is smaller than 10 million or so.
Following is the algorithm to find all the prime numbers less than or equal to a
given integer n by the Eratosthene’s method:
When the algorithm terminates, all the numbers in the list that are not marked
are prime.

-5-
(三) 演算法則
1. 第一個演算法(Algorithm)

int PrimeTest(int N)

for (int i = 2; i*i <= N; ++i)

if(N%i == 0)

return 0;

return 1;

i. 演算法時間複雜度(time complexity)

O(√N)

演算法空間複雜度(space complexity)

O(1)

2. 第二個演算法(Algorithm)

function: FermatPrimalityTesting(int N):

pick a random integer k //not too less. not too high.

LOOP: repeat k times:

-6-
 pick a random integer X in range (1,N-1)

if(X^(N-1)%N != 1):

return composite

return probably prime

i. 演算法時間複雜度(time complexity)

O(k \cdot \log N)

ii. 演算法空間複雜度(space complexity)

O(1)

3 第三個演算法(Algorithm)

function: MillerRabin_PrimalityTesting(int N):

if N%2 = 0:

return composite

write N-1 as (2^R . D) where D is odd number

pick a random integer k //not too less. not too high.

LOOP: repeat k times:

pick a random integer A in range [2,N-2]

X = A^D % N

if X = 1 or X = N-1:

continue LOOP

for i from 1 to r-1:

X = X^2 % N

-7-
 if X = 1:

return composite

if X = N-1:

continue LOOP

return composite

return probably prime

i. 演算法時間複雜度(time complexity)

O(k \cdot \log N)…

ii. 演算法空間複雜度(space complexity)

O(1)

4. 第四個演算法

A[N] = {0}

for i from 2 to sqrt(N):

if A[i] = 0:

for j from 2 to N:

if i*j > N:

break

A[i*j] = 1

i. 演算法時間複雜度(time complexity)

O(N \log N)

ii. 演算法空間複雜度(space complexity)

O(N)

-8-
(四) 程式設計環境架構
程式設計語言、工具、環境與電腦硬體等規格說明…

1. 程式語言

C++

2. 程式開發工具

Visual Studio 2019

3. 電腦硬體

CPU: Intel i7,

Main Memory: 24GB

-9-
(五) 程式 (含 source code, input code, and output code)
程式含 source code, input code, and output code 等…

1. 主程式
1.BASIC

#include <iostream>

#include <cmath>

using namespace std;

// Function to check if a number is prime

bool isPrime(long long N)

if (N <= 1) {

return false;

if (N == 2 || N == 3) {

return true;

if (N % 2 == 0 || N % 3 == 0) {

return false;

for (long long i = 5; i * i <= N; i += 6) {

if (N % i == 0 || N % (i + 2) == 0) {

return false;

return true;

-10-
 }

int main()

int T;

cout << "enter how many cases you want to test : ";

cin >> T; // Number of test cases

for (int t = 0; t < T; t++)

long long N;

cin >> N; // Read the number for each test case

if (isPrime(N)) {

cout << "prime" << endl;

else {

cout << "composite" << endl;

return 0;

system("pause");

2. FERMAT

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

-11-
// Function to perform modular exponentiation (X^Y % N)

long long mod_exp(long long base, long long exp, long long mod) {

long long result = 1;

base = base % mod;

while (exp > 0) {

if (exp % 2 == 1) // If exp is odd, multiply base with result

result = (result * base) % mod;

exp = exp >> 1; // Divide exp by 2

base = (base * base) % mod; // Square the base

return result;

// Fermat Primality Test function

string fermat_primality_test(long long N, int k = 5)

// Handle small cases

if (N <= 1) return "composite";

if (N == 2 || N == 3) return "prime";

// Perform the test k times

for (int i = 0; i < k; i++) {

-12-
 long long X = 2 + rand() % (N - 3); // Random integer X in range [2, N-2]

if (mod_exp(X, N - 1, N) != 1)

return "composite";

return "prime";

int main() {

srand(time(0)); // Seed for random number generator

int T; // Number of test cases

cout << "enter how many cases you want to test : ";

cin >> T;

for (int i = 0; i < T; i++) {

long long N;

cin >> N;

cout << fermat_primality_test(N) << endl;

return 0;

3. MILLER

#include <iostream>

-13-
#include <cstdlib>

#include <ctime>

using namespace std;

// Function to perform modular exponentiation

// It returns (x^y) % p

long long power(long long x, long long y, long long p) {

long long res = 1; // Initialize result

x = x % p; // Update x if it is more than or equal to p

while (y > 0) {

// If y is odd, multiply x with the result

if (y & 1)

res = (res * x) % p;

// y must be even now

y = y >> 1; // y = y/2

x = (x * x) % p; // Change x to x^2

return res;

// This function is called for all k trials.

// It returns false if n is composite and returns true if n is probably prime.

// d is an odd number such that d*2^r = n-1 for some r >= 1.

-14-
bool millerTest(long long n, long long d) {

// Pick a random number in [2..n-2]

// Corner cases make sure that n > 4

long long a = 2 + rand() % (n - 4);

// Compute a^d % n

long long x = power(a, d, n);

if (x == 1 || x == n - 1)

return true;

// Keep squaring x while one of the following doesn't happen:

// (i) d does not reach n-1

// (ii) (x^2) % n is not 1

// (iii) (x^2) % n is not n-1

while (d != n - 1) {

x = (x * x) % n;

d *= 2;

if (x == 1) return false;

if (x == n - 1) return true;

// Return composite

return false;

-15-
// It returns false if n is composite and returns true if n is probably prime.

// k is an input parameter that determines the accuracy level. Higher value of k means more
accuracy.

bool isPrime(long long n, int k) {

// Handle base cases

if (n <= 1 || n == 4) return false;

if (n <= 3) return true;

// Find d such that n-1 = d * 2^r

long long d = n - 1;

while (d % 2 == 0)

d /= 2;

// Perform k iterations of the Miller-Rabin test

for (int i = 0; i < k; i++)

if (!millerTest(n, d))

return false;

return true;

int main() {

srand(time(0)); // Seed for random number generation

int T; // Number of test cases

-16-
 cout << "enter how many cases you want to test : ";

cin >> T;

while (T--) {

long long N;

cin >> N;

// Number of iterations for Miller-Rabin test

int accuracy = 5;

if (isPrime(N, accuracy))

cout << "prime" << endl;

else

cout << "composite" << endl;

return 0;

4. SIEVE

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

vector<bool> sieve_of_eratosthenes(long long limit) {

-17-
 vector<bool> is_prime(limit + 1, true);

is_prime[0] = is_prime[1] = false; // 0 and 1 are not prime

for (long long i = 2; i * i <= limit; i++) {

if (is_prime[i]) {

for (long long j = i * i; j <= limit; j += i) {

is_prime[j] = false;

return is_prime;

bool is_prime(long long n) {

if (n <= 1) return false;

if (n <= 3) return true;

if (n % 2 == 0 || n % 3 == 0) return false;

for (long long i = 5; i * i <= n; i += 6) {

if (n % i == 0 || n % (i + 2) == 0) return false;

return true;

int main() {

int T;

-18-
cout << "enter how many cases you want to test : ";

cin >> T;

while (T--) {

long long N;

cin >> N;

if (N <= 10000000) { // Use sieve for smaller numbers

vector<bool> primes = sieve_of_eratosthenes(N);

if (primes[N]) {

cout << "prime" << endl;

else {

cout << "composite" << endl;

else { // Use direct primality check for larger numbers

if (is_prime(N)) {

cout << "prime" << endl;

else {

cout << "composite" << endl;

-19-
 return 0;

2. Input Code Format

Three of examples for input use are in below….

(1) 3

(2) 122

(3) 5

(4) 3

3. Output Code Format

Three of examples for output use are in below….

(1) composite

(2) prime

(3) prime

-20-
(五) 執行結果、討論與心得
1. 執行結果

input use are in below….

(1) 3

(2) 122

(3) 5

(4) 3

output use are in below….

(1) composite

(2) prime

(3) prime

2. 討論

方法 2 和 3 機率:

(ii) FERMAT：

對於某些合數，費馬測試會錯誤地標記它們為質數，這些數稱為「費馬偽質數」。例如，561 是一個費馬偽質數。根據 𝑘 的選擇，成功率會

有所不同。

(iii) MILLER：

𝑘 可以進一步降低誤判的機率。
米勒-拉賓質數測試相對於費馬測試來說具有更高的成功率。實際上，選擇適當的隨機數可以使得它的誤判率非常低。通常情況下，增加測試次數

執行時間、問題大小等問題討論! 利用 MS Excel 畫出問題大小與執行時間的關係!

(1) Running Time

-21-
 (2) Problem size n

i. 不適合大數字

ii. 執行時間隨著 𝑛 增加而線性增長，但因為對大數的隨機化處理，實際執行時間可能會稍有變化。

iii 同 ii

iv. 對於大範圍的質數生成，這種方法的效率較高

(3) 最大 Mersenne Prime Number

282589933−1

3. 心得

在實作 Primality Testing 的過程中，我對時間複雜度與實際執行時間之間的關係有了深刻的理解。雖然理論上可以透過時間複雜度來預測演算

法的效率，但實際執行時間往往受到硬體性能和編程語言的影響。在多次測試中，我發現即使是相同複雜度的演算法，執行時間可能有顯著差異，因此
在選擇演算法時，實際性能測試顯得尤為重要。這次經驗讓我明白，理解時間複雜度與實際執行時間的差異，不僅對演算法設計至關重要，也對未來的
學習與應用提共了寶貴的指導。

-22-
參考文獻
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, "Introduction
to Algorithms," Third Edition, The MIT Press, 2009.
[2] R.C.T. Lee, S.S. Tseng, R.C. Chang, and Y.T.Tsai, "Introduction to the Design and Analysis of
Algorithms," McGraw-Hill, 2005.
[3] Anany V. Levitin, "Introduction to the Design and Analysis of Algorithms," 3rd Edition,
Addison Wesley, 2012.
[4] Richard Neapolitan and Kumarss Naimipour, "Foundations of Algorithms," Fourth Edition,
Jones and Bartlett Publishers, 2010.
[5] https://www.hackerearth.com/practice/math/number-theory/primality-tests/tutorial/
[6] …

-23-