หาตัวประกอบโดยการทดลองหาร

เราสั่งให้คอมพิวเตอร์ทำงานแทนเราในการหาว่าตัวเลข $n$ มีตัวประกอบอะไรบ้างโดยทดลองเอาตัวเลขต่างๆที่ไม่เกิน $n$ มาทดลองหารดูว่าหารลงตัวหรือไม่ เช่นถ้า $n$ คือ 24 ก็จะหาว่ามีตัวประกอบอะไรบ้าง:

In [1]:
n = 24
for i in range(1,n+1): #ลองเอาเลข 1, 2, 3,..., 24 มาทดลองหาร
    if n % i == 0: #ถ้า n หาร i แล้วเศษเท่ากับศูนย์ (ก็คือหารลงตัว)
        print(i) #พิมพ์ i ที่หารลงตัวออกมา
1
2
3
4
6
8
12
24

ทดลองกับ $n$ เท่ากับ 1019 แล้วพบว่าตัวประกอบมีเพียง 1 และ 1019 เอง แสดงว่ามันเป็นจำนวนเฉพาะ:

In [2]:
n = 1019
for i in range(1,n+1): #ลองเอาเลข 1, 2, 3,..., 1019 มาทดลองหาร
    if n % i == 0: #ถ้า n หาร i แล้วเศษเท่ากับศูนย์ (ก็คือหารลงตัว)
        print(i) #พิมพ์ i ที่หารลงตัวออกมา
1
1019

ถ้าเราจะหาตัวประกอบของตัวเลขหลายๆตัว เราควรสร้างฟังก์ชั่นไว้สำหรับป้อนค่า $n$ ต่างๆเข้าไป:

In [3]:
def แสดงตัวประกอบ(n):
    """
    พิมพ์ตัวประกอบของ n ออกมาให้ดู
    โดยทดลองหาร n ด้วย 1, 2, 3,..., n
    ว่าหารลงตัวหรือไม่
    """
    for i in range(1,n+1):
        if n % i == 0:
            print(i)

ทดลองกับค่า $n$ ต่างๆดู:

In [4]:
แสดงตัวประกอบ(25)
1
5
25
In [5]:
แสดงตัวประกอบ(360)
1
2
3
4
5
6
8
9
10
12
15
18
20
24
30
36
40
45
60
72
90
120
180
360
In [6]:
แสดงตัวประกอบ(1000)
1
2
4
5
8
10
20
25
40
50
100
125
200
250
500
1000
In [7]:
แสดงตัวประกอบ(123456789)
1
3
9
3607
3803
10821
11409
32463
34227
13717421
41152263
123456789

เราจะพบว่าเมื่อตัวเลข $n$ ใหญ่ขึ้น ฟังก์ชั่น $แสดงตัวประกอบ()$ จะใช้เวลานานขึ้นเรื่อยๆ เราทดลองจับเวลาได้ด้วยคำสั่ง %time ดังนี้

In [8]:
%time แสดงตัวประกอบ(123456789)
1
3
9
3607
3803
10821
11409
32463
34227
13717421
41152263
123456789
CPU times: user 6.83 s, sys: 24.9 ms, total: 6.86 s
Wall time: 6.87 s

ผลข้างบนแสดงว่า $แสดงตัวประกอบ(123456789)$ ใช้เวลาหลายวินาทีในการทำงาน

เราสังเกตว่าจริงๆแล้วเวลาเราหาตัวประกอบของ $n$ เราไม่ต้องทดลองหารตั้งแต่ $1$ ไปจนถึง $n$ ก็ได้ถ้าเราเก็บผลลัพธ์การหารไว้ด้วย เช่นถ้าเราหาตัวประกอบของ 24 เมื่อเราเอา 1 ไปหารแล้วได้ผลลัพธ์ 24 เราก็รู้แล้วว่าทั้ง 1 และ 24 เป็นตัวประกอบของ 24

เช่นเดียวกันเมื่อเราเอา 2 ไปหารแล้วได้ผลลัพธ์ 12 เราก็รู้ว่าทั้ง 2 และ 12 เป็นตัวประกอบของ 24

เมื่อเราเอา 3 ไปหารแล้วได้ผลลัพธ์ 8 เราก็รู้ว่าทั้ง 8 และ 3 เป็นตัวประกอบของ 24

เมื่อเราเอา 4 ไปหารแล้วได้ผลลัพธ์ 6 เราก็รู้ว่าทั้ง 4 และ 6 เป็นตัวประกอบของ 24

เมื่อเราจะเอา 6 ไปหาร เราก็พบว่าเรารู้อยู่แล้วว่า 6 เป็นตัวประกอบอยู่แล้วตอนเราหารด้วย 4

แสดงว่าเราไม่จำเป็นต้องลองหารด้วยตัวเลขที่ใหญ่ขึ้นไปอีกแล้วเพราะว่าถ้ามีพวกมันเป็นตัวประกอบของ 24 มันต้องถูกพบมาแล้วเมื่อเราลองหารด้วยตัวประกอบเล็กๆ

ถ้าเราคิดต่อไปในที่สุดเราจะพบว่าเมื่อเราหาตัวประกอบของ $n$ เรามีความจำเป็นที่จะทดลองหารตั้งแต่ $1$ ไปถึง $\sqrt{n}$ เท่านั้น เช่นถ้า $n$ คือ 24, $\sqrt{24} \approx 4.9$ เราจึงทดลองหารแค่ 1, 2, 3, 4, 5 ก็พอแล้ว

เราจะเห็นความแตกต่างชัดเจนเมื่อ $n$ มีขนาดใหญ่ๆ เช่นถ้า $n$ มีขนาดสักหนึ่งล้าน ถ้าเราทดลองหารด้วยวิธีเดิมเราต้องลองหารประมาณหนึ่งล้านครั้ง แต่ถ้าเราทดลองหารถึง $\sqrt{n}$ เราจะหารแค่ประมาณหนึ่งพันครั้งเท่านั้น แตกต่างกันถึงพันเท่า

เราสร้างฟังก์ชั่น $แสดงตัวประกอบ2()$ ที่ทดลองหารถึงประมาณ $\sqrt{n}$ เท่านั้นดังนี้:

In [9]:
#เราใช้โมดูล math โดย import math เข้ามา
#เพื่อใช้ math.sqrt เพื่อหารสแควรูทของ n
#และใช้ math.ceil เพื่อปัดเศษขึ้น

import math
def แสดงตัวประกอบ2(n):
    """
    พิมพ์ตัวประกอบของ n ออกมาให้ดู
    โดยทดลองหาร n ด้วย 1, 2, 3,..., sqrt(n)
    ว่าหารลงตัวหรือไม่
    """
    for i in range(1,math.ceil(math.sqrt(n))+1):
        if n % i == 0:
            print(i, n//i) # n//i คือผลลัพธ์การหาร n ด้วย i แบบเป็นเลขจำนวนเต็ม
In [10]:
แสดงตัวประกอบ2(12)
1 12
2 6
3 4
4 3
In [11]:
แสดงตัวประกอบ2(25)
1 25
5 5

ทดลองจับเวลาเมื่อ $n$ มีขนาดใหญ่ๆ:

In [12]:
%time แสดงตัวประกอบ2(123456789)
1 123456789
3 41152263
9 13717421
3607 34227
3803 32463
10821 11409
CPU times: user 895 µs, sys: 136 µs, total: 1.03 ms
Wall time: 947 µs

การลองหารถึง $\sqrt{n}$ พบว่าใช้เวลาหลักเศษส่วนพันของวินาทีเมื่อ $n$ มี 9 หลัก เร็วกว่าตอนทดลองหารจนถึง $n$ หลายพันเท่า

ฟังก์ชั่น $แสดงตัวประกอบ()$ และ $แสดงตัวประกอบ2()$ มีข้อเสียคือแสดงผลว่ามีตัวประกอบอะไรบ้าง ไม่ได้ส่งรายการตัวประกอบเหล่านั้นออกมาเพื่อให้เอาไปทำอะไรต่อง่ายๆ และอาจแสดงผลซ้ำด้วย ดังนั้นเราควรสร้างฟังก์ชั่นใหม่ที่ส่งรายการตัวประกอบที่ไม่ซ้ำออกมาให้ไปใช้ต่อง่ายๆดีกว่า ยกตัวอย่างเช่น:

In [13]:
def ตัวประกอบ(n):
    """
    ส่งลิสต์ที่มีตัวประกอบของ n ออกมาให้
    โดยทดลองหาร n ด้วย 1, 2, 3,..., sqrt(n)
    ว่าหารลงตัวหรือไม่
    """
    factors = [] #เป็นลิสต์เก็บตัวประกอบต่างๆเพื่อส่งต่อไปให้ใช้ง่ายๆ
    for i in range(1,math.ceil(math.sqrt(n)) + 1):
        if n % i == 0: #ถ้า i หารลงตัว เก็บ i และ n//i ในลิสต์ตัวประกอบ
            factors.append(i) 
            factors.append(n//i)
    factors = set(factors) #เปลี่ยนลิสต์เป็นเซ็ตเพื่อไม่ให้ตัวประกอบซ้ำกัน
    return sorted(list(factors)) #ส่งรายการตัวประกอบที่พบออกมาเป็นลิสต์ที่เรียงลำดับจากน้อยไปมาก
In [14]:
ตัวประกอบ(12)
Out[14]:
[1, 2, 3, 4, 6, 12]
In [15]:
ตัวประกอบ(1024)
Out[15]:
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
In [16]:
ตัวประกอบ(2019)
Out[16]:
[1, 3, 673, 2019]
In [17]:
ตัวประกอบ(123456789)
Out[17]:
[1,
 3,
 9,
 3607,
 3803,
 10821,
 11409,
 32463,
 34227,
 13717421,
 41152263,
 123456789]
In [18]:
#ลองพิมพ์ตัวประกอบของเลข 1 ถึง 100
#ใช้ list comprehension เปลี่ยนตัวเลขเป็นสตริงด้วย [str(i) for i in ตัวประกอบ(n)]
#เชื่อมสตริงตัวเลขด้วยคอมม่าด้วยวิธี ','.join(...)
#แสดงผลด้วย f-string
for n in range(1,100+1):
    print(f"ตัวประกอบของ {n} คือ {', '.join([str(i) for i in ตัวประกอบ(n)])}")
ตัวประกอบของ 1 คือ 1
ตัวประกอบของ 2 คือ 1, 2
ตัวประกอบของ 3 คือ 1, 3
ตัวประกอบของ 4 คือ 1, 2, 4
ตัวประกอบของ 5 คือ 1, 5
ตัวประกอบของ 6 คือ 1, 2, 3, 6
ตัวประกอบของ 7 คือ 1, 7
ตัวประกอบของ 8 คือ 1, 2, 4, 8
ตัวประกอบของ 9 คือ 1, 3, 9
ตัวประกอบของ 10 คือ 1, 2, 5, 10
ตัวประกอบของ 11 คือ 1, 11
ตัวประกอบของ 12 คือ 1, 2, 3, 4, 6, 12
ตัวประกอบของ 13 คือ 1, 13
ตัวประกอบของ 14 คือ 1, 2, 7, 14
ตัวประกอบของ 15 คือ 1, 3, 5, 15
ตัวประกอบของ 16 คือ 1, 2, 4, 8, 16
ตัวประกอบของ 17 คือ 1, 17
ตัวประกอบของ 18 คือ 1, 2, 3, 6, 9, 18
ตัวประกอบของ 19 คือ 1, 19
ตัวประกอบของ 20 คือ 1, 2, 4, 5, 10, 20
ตัวประกอบของ 21 คือ 1, 3, 7, 21
ตัวประกอบของ 22 คือ 1, 2, 11, 22
ตัวประกอบของ 23 คือ 1, 23
ตัวประกอบของ 24 คือ 1, 2, 3, 4, 6, 8, 12, 24
ตัวประกอบของ 25 คือ 1, 5, 25
ตัวประกอบของ 26 คือ 1, 2, 13, 26
ตัวประกอบของ 27 คือ 1, 3, 9, 27
ตัวประกอบของ 28 คือ 1, 2, 4, 7, 14, 28
ตัวประกอบของ 29 คือ 1, 29
ตัวประกอบของ 30 คือ 1, 2, 3, 5, 6, 10, 15, 30
ตัวประกอบของ 31 คือ 1, 31
ตัวประกอบของ 32 คือ 1, 2, 4, 8, 16, 32
ตัวประกอบของ 33 คือ 1, 3, 11, 33
ตัวประกอบของ 34 คือ 1, 2, 17, 34
ตัวประกอบของ 35 คือ 1, 5, 7, 35
ตัวประกอบของ 36 คือ 1, 2, 3, 4, 6, 9, 12, 18, 36
ตัวประกอบของ 37 คือ 1, 37
ตัวประกอบของ 38 คือ 1, 2, 19, 38
ตัวประกอบของ 39 คือ 1, 3, 13, 39
ตัวประกอบของ 40 คือ 1, 2, 4, 5, 8, 10, 20, 40
ตัวประกอบของ 41 คือ 1, 41
ตัวประกอบของ 42 คือ 1, 2, 3, 6, 7, 14, 21, 42
ตัวประกอบของ 43 คือ 1, 43
ตัวประกอบของ 44 คือ 1, 2, 4, 11, 22, 44
ตัวประกอบของ 45 คือ 1, 3, 5, 9, 15, 45
ตัวประกอบของ 46 คือ 1, 2, 23, 46
ตัวประกอบของ 47 คือ 1, 47
ตัวประกอบของ 48 คือ 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
ตัวประกอบของ 49 คือ 1, 7, 49
ตัวประกอบของ 50 คือ 1, 2, 5, 10, 25, 50
ตัวประกอบของ 51 คือ 1, 3, 17, 51
ตัวประกอบของ 52 คือ 1, 2, 4, 13, 26, 52
ตัวประกอบของ 53 คือ 1, 53
ตัวประกอบของ 54 คือ 1, 2, 3, 6, 9, 18, 27, 54
ตัวประกอบของ 55 คือ 1, 5, 11, 55
ตัวประกอบของ 56 คือ 1, 2, 4, 7, 8, 14, 28, 56
ตัวประกอบของ 57 คือ 1, 3, 19, 57
ตัวประกอบของ 58 คือ 1, 2, 29, 58
ตัวประกอบของ 59 คือ 1, 59
ตัวประกอบของ 60 คือ 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
ตัวประกอบของ 61 คือ 1, 61
ตัวประกอบของ 62 คือ 1, 2, 31, 62
ตัวประกอบของ 63 คือ 1, 3, 7, 9, 21, 63
ตัวประกอบของ 64 คือ 1, 2, 4, 8, 16, 32, 64
ตัวประกอบของ 65 คือ 1, 5, 13, 65
ตัวประกอบของ 66 คือ 1, 2, 3, 6, 11, 22, 33, 66
ตัวประกอบของ 67 คือ 1, 67
ตัวประกอบของ 68 คือ 1, 2, 4, 17, 34, 68
ตัวประกอบของ 69 คือ 1, 3, 23, 69
ตัวประกอบของ 70 คือ 1, 2, 5, 7, 10, 14, 35, 70
ตัวประกอบของ 71 คือ 1, 71
ตัวประกอบของ 72 คือ 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72
ตัวประกอบของ 73 คือ 1, 73
ตัวประกอบของ 74 คือ 1, 2, 37, 74
ตัวประกอบของ 75 คือ 1, 3, 5, 15, 25, 75
ตัวประกอบของ 76 คือ 1, 2, 4, 19, 38, 76
ตัวประกอบของ 77 คือ 1, 7, 11, 77
ตัวประกอบของ 78 คือ 1, 2, 3, 6, 13, 26, 39, 78
ตัวประกอบของ 79 คือ 1, 79
ตัวประกอบของ 80 คือ 1, 2, 4, 5, 8, 10, 16, 20, 40, 80
ตัวประกอบของ 81 คือ 1, 3, 9, 27, 81
ตัวประกอบของ 82 คือ 1, 2, 41, 82
ตัวประกอบของ 83 คือ 1, 83
ตัวประกอบของ 84 คือ 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84
ตัวประกอบของ 85 คือ 1, 5, 17, 85
ตัวประกอบของ 86 คือ 1, 2, 43, 86
ตัวประกอบของ 87 คือ 1, 3, 29, 87
ตัวประกอบของ 88 คือ 1, 2, 4, 8, 11, 22, 44, 88
ตัวประกอบของ 89 คือ 1, 89
ตัวประกอบของ 90 คือ 1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90
ตัวประกอบของ 91 คือ 1, 7, 13, 91
ตัวประกอบของ 92 คือ 1, 2, 4, 23, 46, 92
ตัวประกอบของ 93 คือ 1, 3, 31, 93
ตัวประกอบของ 94 คือ 1, 2, 47, 94
ตัวประกอบของ 95 คือ 1, 5, 19, 95
ตัวประกอบของ 96 คือ 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96
ตัวประกอบของ 97 คือ 1, 97
ตัวประกอบของ 98 คือ 1, 2, 7, 14, 49, 98
ตัวประกอบของ 99 คือ 1, 3, 9, 11, 33, 99
ตัวประกอบของ 100 คือ 1, 2, 4, 5, 10, 20, 25, 50, 100

การเขียนเลขจำนวนเต็มบวกเป็นผลคูณของเลขจำนวนเฉพาะ (Prime Factorization)

มีความจริงที่ว่าตัวเลขเต็มบวกใดๆ(ยกเว้น 1)จะเป็นผลคูณของเลขจำนวนเฉพาะได้แบบเดียวเท่านั้นถ้าไม่นับการสลับตำแหน่ง (Fundamental Theorem of Arithmetic) เช่น 12 = 2x2x3, 100 = 2x2x5x5, 256 = 2x2x2x2x2x2x2x2 เป็นต้น

เราสามารถหารูปแบบได้ด้วยการเอาตัวเลขตั้งแต่ 2, 3,..., $\sqrt{n}$ ไปลองหาร n ซ้ำๆทีละตัวจนหารต่อไม่ได้แล้วลองหารด้วยเลขต่อไป เช่นถ้าเราจะหาว่า 12 เขียนเป็นจำนวนเฉพาะคูณกันได้อย่างไร เราก็จะทดลองหารด้วย 2, 3, 4 (เพราะ $\sqrt{12} \approx 3.5$ จึงลองหารถึง 4) พอหารด้วย 2 ครั้งแรกลงตัวได้ 6 ก็เอา 6 หารด้วย 2 ต่ออีก หารลงตัวเหลือ 3 แต่ก็หารต่อด้วย 2 ไม่ลงตัวแล้ว จึงลองเอา 3 มาหาร ได้ผลเท่ากับ 1 หารต่อด้วย 3 ไม่ลงตัวจึงเอา 4 มาลองหารก็หารไม่ลงตัว เราดูว่าเราหารด้วย 2, 3, 4 ลงตัวกี่ครั้งก็เก็บเลขที่หารลงตัวนั้นไว้คือ 2, 2, 3 ดั้งนั้น 12 = 2x2x3

เราสามารถสั่งให้คอมพิวเตอร์หารูปแบบประเภทนี้สำหรับเลขจำนวนเต็มบวกใดๆได้ดังนี้:

In [19]:
def ตัวประกอบเฉพาะ(n):
    """
    หาตัวประกอบที่เป็นจำนวนเฉพาะของจำนวนเต็มบวก n 
    ถ้าเอาผลที่ได้คูณกันจะได้ค่า n
    เช่น ตัวประกอบเฉพาะ(12) คือ [2, 2, 3]
    """
    if n < 0:
        return [] #ไม่คำนวณจำนวนลบ
    if n == 1:
        return [1] #ตัวประกอบของ 1 คือ 1 
    factors = [] #ลิสต์ที่จะเก็บตัวประกอบต่างๆ
    i = 2  #เริ่มโดยลองเอา i = 2 มาหาร n ดู
    while i*i <= n: #เราจะหารไม่เกิน sqrt(n)
        while n%i == 0: #ถ้าหารลงตัว เก็บตัวหารไว้ในคำตอบ ลดขนาด n ลงเป็นผลลัพธ์ของการหาร
            factors.append(i)
            n = n//i
        i = i+1 #เมื่อ i หารลงตัวต่อไม่ได้แล้วให้ลอง i ตัวต่อไปมาหารดู
    if n > 1: #ถ้าตัวหารที่ควรทดลองลองหมดแล้วแล้วผลลัพธ์จากการหารยังไม่ใช่ 1 แสดงว่ามันก็เป็นตัวประกอบเฉพาะด้วย
        factors.append(n)
    return factors #ส่งลิสต์ที่มีตัวประกอบที่หาได้ออกมาเป็นคำตอบ
In [20]:
ตัวประกอบเฉพาะ(57946714)
Out[20]:
[2, 7, 7, 43, 13751]
In [21]:
ตัวประกอบเฉพาะ(100)
Out[21]:
[2, 2, 5, 5]
In [22]:
ตัวประกอบเฉพาะ(1024)
Out[22]:
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
In [23]:
ตัวประกอบเฉพาะ(123456789)
Out[23]:
[3, 3, 3607, 3803]
In [24]:
#ลองเอาคำตอบคูณกันว่าได้เท่ากับตัวตั้งไหม
3*3*3607*3803
Out[24]:
123456789
In [25]:
#ลองหาตัวประกอบเลข 15 หลักดู จับเวลาดูด้วย
%time ตัวประกอบเฉพาะ(111_111_111_111_111)
CPU times: user 213 µs, sys: 1 µs, total: 214 µs
Wall time: 217 µs
Out[25]:
[3, 31, 37, 41, 271, 2906161]
In [26]:
#วิธีใช้ numpy.prod คูณตัวเลขในลิสต์ (prod ย่อมาจาก product แปลว่าคูณ)

import numpy
numpy.prod([3, 31, 37, 41, 271, 2906161])
Out[26]:
111111111111111
In [27]:
#ทดสอบดูว่าผลคูณของคำตอบจาก ตัวประกอบเฉพาะ(n) เท่ากับ n เสมอ
#ทดสอบด้วยเลขสุ่มหลายๆตัว ถ้ามีตัวไหนไม่ได้คำตอบอย่างที่ควรเป็นให้พิมพ์ออกมา n คืออะไร

import random
trials = 10_000
max_n = 1_000_000_000
everything_OK = True
for i in range(trials):
    n = random.randint(1,max_n)
    if numpy.prod(ตัวประกอบเฉพาะ(n)) != n:
        print(f"มีคำตอบที่ผิดเมื่อ n = {n}, {ตัวประกอบเฉพาะ(n)}")
        everything_OK = False
if everything_OK:
    print(f"ทดลองเลขในช่วง 1 ถึง {max_n:,} เป็นจำนวน {trials:,} ครั้ง ไม่พบสิ่งผิดปกติ")
ทดลองเลขในช่วง 1 ถึง 1,000,000,000 เป็นจำนวน 10,000 ครั้ง ไม่พบสิ่งผิดปกติ

วิธีทดลองหารเพื่อหาตัวประกอบนี้เป็นวิธีที่เข้าใจง่ายที่สุด ยังมีวิธีอื่นๆอีกหลายๆวิธีที่สามารถทำงานได้เร็วกว่ามากมาย ถ้าสนใจลองไปดูที่ Factoring algorithms ดูนะครับ