โปรแกรมหาตัวประกอบ

In [1]:
# หาตัวประกอบของ 100 
# ทำโดยทดลองหาร 100 ด้วยเลข 1 ถึง 100
# ถ้าหารลงตัวก็พิมพ์ตัวเลขที่หารลงตัวออกมา

x = 100
for i in range(1,x+1):
    if x % i == 0:
        print(i)
1
2
4
5
10
20
25
50
100
In [2]:
# ทำเป็นฟังก์ชั่นที่พิมพ์ตัวประกอบของเลข x

def find_factors(x):
    for i in range(1,x+1):
        if x % i == 0:
            print(i)
In [3]:
find_factors(12)
1
2
3
4
6
12
In [4]:
# ฟังก์ชั่นด้านบนพิมพ์ตัวประกอบออกมาเท่านั้น
# เราไม่สามารถเอาตัวประกอบที่หามาไปใช้ทำประโยชน์อย่างอื่นได้
# เราจึงปรับปรุงฟังก์ชั่นใหม่ให้เก็บตัวประกอบที่หามาได้ใส่ไว้ในลิสต์ชื่อ result
# แล้วส่งลิสต์ result ออกมาให้ผู้เรียกฟังก์ชั่น find_factors
# ผู้เรียกฟังก์ชั่นสามารถเอาตัวประกอบในลิสต์ result ไปทำประโยชน์อื่นๆต่อได้

def find_factors(x):
    result = []
    for i in range(1,x+1):
        if x % i == 0:
            result.append(i)
    return(result)
In [5]:
find_factors(12)
Out[5]:
[1, 2, 3, 4, 6, 12]
In [6]:
# เก็บตัวประกอบของ 12 ไว้ในตัวแปรลิสต์ชื่อ factors
# ใช้ len(factors) นับจำนวนตัวประกอบของ 12

factors = find_factors(12)
len(factors)
Out[6]:
6
In [7]:
# เราใช้คำสั่ง %time เพื่อจับเวลาการทำงานฟังก์ชั่นได้
%time find_factors(123456789)
CPU times: user 6 s, sys: 7.82 ms, total: 6.01 s
Wall time: 6.01 s
Out[7]:
[1,
 3,
 9,
 3607,
 3803,
 10821,
 11409,
 32463,
 34227,
 13717421,
 41152263,
 123456789]

ดัดแปลงให้ทำงานเร็วขึ้นอีก

เวลาหาตัวประกอบแบบด้านบน เราสังเกตว่าถ้าเราเก็บผลลัพธ์การหารไว้ด้วย เราก็ไม่จำเป็นต้องลองหารด้วยตัวเลขที่มากกว่า $\sqrt{x}$ เพราะทุกครั้งที่หารลงตัวเราจะได้ตัวประกอบมาสองตัวที่คูณกันแล้วเท่ากับ $x$ โดยที่ตัวหนึ่งจะมีขนาดไม่เกิน $\sqrt{x}$ และอีกตัวจะมีขนาดมากกว่าหรือเท่ากับ $\sqrt{x}$

ยกตัวอย่างเช่นหาตัวประกอบของ 12

$\sqrt{12}$ $\approx$ 3.46

เราก็ลองหาร 12 ด้วย 1, 2, ... แต่ไม่เกิน 3.46

12 หารด้วย 1 ลงตัวและ 12/1 = 12 ดังนั้น 1 และ 12 เป็นตัวประกอบของ 12

12 หารด้วย 2 ลงตัวและ 12/2 = 6 ดังนั้น 2 และ 6 เป็นตัวประกอบของ 12

12 หารด้วย 3 ลงตัวและ 12/3 = 4 ดังนั้น 3 และ 4 เป็นตัวประกอบของ 12

เราไม่ต้องลองหารด้วย 4, 5, 6, 7, ..., 11, 12 แล้วเพราะเกิน $\sqrt{12}$ ไปแล้ว

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

In [8]:
# ต้อง import math เพื่อใช้ฟังก์ชั่น math.sqrt() มาหารากที่สอง

import math

math.sqrt(12)
Out[8]:
3.4641016151377544
In [9]:
# ทำความรู้จัก math.ceil() ที่ปัดเศษขึ้นไปเป็นจำนวนเต็ม

math.ceil(3.5)
Out[9]:
4
In [10]:
# ทำความรู้จัก math.floor() ที่ปัดเศษลงมาเป็นจำนวนเต็ม
math.floor(3.5)
Out[10]:
3
In [11]:
# การหารปกติด้วย / จะได้ผลลัพธ์เป็นเลขทศนิยม

12 / 3
Out[11]:
4.0
In [12]:
# การหารด้วย // จะได้ผลลัพธ์เป็นเลขจำนวนเต็ม เศษถูกทิ้งไป
12 // 3
Out[12]:
4
In [13]:
14 // 3
Out[13]:
4
In [14]:
# ทำการทดลองหารถึง sqrt(x)
# มีบั๊กในกรณีที่ sqrt(x) เป็นจำนวนเต็ม จะให้ตัวประกอบตัวที่มากที่สุดซ้ำสองครั้ง

import math

def find_factors_2(x):
    result = []
    upper = math.ceil(math.sqrt(x)) + 1  #เราจะไล่ตัวหารจาก 1 ไป sqrt(x) โดยปัดขึ้นเป็นจำนวนเต็ม
    for i in range(1, upper):
        if x % i == 0:
            result.append(i)
            result.append(x // i)
    return(result)
In [15]:
# ทดลองหาตัวประกอบของ 100
# สังเกตว่ามีตัวประกอบซ้ำคือมี 10 สองตัว

find_factors_2(100)
Out[15]:
[1, 100, 2, 50, 4, 25, 5, 20, 10, 10]
In [16]:
# เพื่อแก้ปัญหาตัวประกอบซ้ำ เราจะใช้ set มาครอบลิสต์คำตอบของเรา
# set(result) จะสร้างสิ่งที่เรียกว่าเซ็ตขึ้นมาจากลิสต์ชื่อ result ของเรา
# เซ็ทเป็นที่เก็บของหลายๆชิ้นของเราคล้ายๆลิสต์ แต่จะเก็บแบบไม่มีของซ้ำกัน
# และของทั้งหลายอาจไม่ได้เรียงลำดับใดๆ
# อ่านเพิ่มเติมเรื่องเซ็ตได้ที่ https://realpython.com/python-sets/

import math

def find_factors_2(x):
    result = []
    upper = math.ceil(math.sqrt(x)) + 1
    for i in range(1, upper):
        if x % i == 0:
            result.append(i)
            result.append(x // i)
    result = set(result) #ทำลิสต์ result ให้กลายเป็นเซ็ต
    return(result)
In [17]:
# ทดลองหาตัวประกอบของ 100
# คราวนี้ตัวประกอบไม่มีซ้ำแล้ว

find_factors_2(100)
Out[17]:
{1, 2, 4, 5, 10, 20, 25, 50, 100}
In [18]:
# เพื่อให้แน่ใจว่าตัวประกอบที่หาออกมาได้จะจัดเรียงลำดับจากน้อยไปมาก
# เราต้องหาทางเรียงลำดับดังนี้:
# 1. set(result) เปลี่ยนลิสต์ result เป็นเซ็ตเพื่อไม่ให้มีตัวประกอบซ้ำ
# 2. list(set(result)) เปลี่ยนเซ็ตจากข้อ 1 ให้กลายเป็นลิสต์อีกครั้ง
#                       เพื่อเตรียมจัดเรียงตัวประกอบจากน้อยไปมาก
# 3. sorted(list(set(result))) จัดเรียงตัวประกอบที่อยู่ในลิสต์ข้อ 2 
#                        ด้วยคำสั่ง sorted() ให้ได้ผลออกมาเป็นลิสต์ใหม่ที่เรียงลำดับแล้ว
# 4. result = sorted(list(set(result))) เอาลิสต์ที่เรียงแล้วเก็บไว้ในตัวแปรชื่อ result

import math

def find_factors_2(x):
    result = []
    upper = math.ceil(math.sqrt(x)) + 1
    for i in range(1, upper):
        if x % i == 0:
            result.append(i)
            result.append(x // i)
    result = sorted(list(set(result)))
    return(result)
In [19]:
# ทดสอบหาตัวประกอบของ 100

find_factors_2(100)
Out[19]:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
In [20]:
# ใช้ %time จับเวลาการทำงานหาตัวประกอบเลข 9 หลัก
# วีธีนี้หาตัวหารจาก 1 ถึง 123456789

%time find_factors(123456789)
CPU times: user 7.08 s, sys: 16.1 ms, total: 7.09 s
Wall time: 7.1 s
Out[20]:
[1,
 3,
 9,
 3607,
 3803,
 10821,
 11409,
 32463,
 34227,
 13717421,
 41152263,
 123456789]
In [21]:
# ใช้ %time จับเวลาการทำงานหาตัวประกอบเลข 9 หลัก
# วีธีนี้หาตัวหารจาก 1 ถึง sqrt(123456789) หรือประมาณ 10,000
# เร็วกว่าวิธีด้านบนประมาณหลายพันถึงหมื่นเท่่า

%time find_factors_2(123456789)
CPU times: user 706 µs, sys: 0 ns, total: 706 µs
Wall time: 709 µs
Out[21]:
[1,
 3,
 9,
 3607,
 3803,
 10821,
 11409,
 32463,
 34227,
 13717421,
 41152263,
 123456789]
In [22]:
# ลองจับเวลาหาตัวประกอบเลข 16 หลัก
# ใช้เวลาไม่นาน
%time find_factors_2(1234567890123456)
CPU times: user 3.02 s, sys: 6.06 ms, total: 3.02 s
Wall time: 3.02 s
Out[22]:
[1,
 2,
 3,
 4,
 6,
 7,
 8,
 12,
 14,
 16,
 21,
 24,
 28,
 32,
 42,
 48,
 49,
 56,
 64,
 84,
 96,
 98,
 112,
 147,
 168,
 192,
 196,
 224,
 294,
 336,
 392,
 448,
 588,
 672,
 784,
 1176,
 1344,
 1568,
 2352,
 3136,
 4704,
 9408,
 301319,
 435503,
 602638,
 871006,
 903957,
 1205276,
 1306509,
 1742012,
 1807914,
 2109233,
 2410552,
 2613018,
 3048521,
 3484024,
 3615828,
 4218466,
 4821104,
 5226036,
 6097042,
 6327699,
 6968048,
 7231656,
 8436932,
 9145563,
 9642208,
 10452072,
 12194084,
 12655398,
 13936096,
 14463312,
 14764631,
 16873864,
 18291126,
 19284416,
 20904144,
 21339647,
 24388168,
 25310796,
 27872192,
 28926624,
 29529262,
 33747728,
 36582252,
 41808288,
 42679294,
 44293893,
 48776336,
 50621592,
 57853248,
 59058524,
 64018941,
 67495456,
 73164504,
 83616576,
 85358588,
 88587786,
 97552672,
 101243184,
 118117048,
 128037882,
 134990912,
 146329008,
 170717176,
 177175572,
 195105344,
 202486368,
 236234096,
 256075764,
 292658016,
 341434352,
 354351144,
 404972736,
 472468192,
 512151528,
 585316032,
 682868704,
 708702288,
 944936384,
 1024303056,
 1365737408,
 1417404576,
 2048606112,
 2834809152,
 4097212224,
 131225328457,
 262450656914,
 393675985371,
 524901313828,
 787351970742,
 918577299199,
 1049802627656,
 1574703941484,
 1837154598398,
 2099605255312,
 2755731897597,
 3149407882968,
 3674309196796,
 4199210510624,
 5511463795194,
 6298815765936,
 6430041094393,
 7348618393592,
 8398421021248,
 11022927590388,
 12597631531872,
 12860082188786,
 14697236787184,
 19290123283179,
 22045855180776,
 25195263063744,
 25720164377572,
 29394473574368,
 38580246566358,
 44091710361552,
 51440328755144,
 58788947148736,
 77160493132716,
 88183420723104,
 102880657510288,
 154320986265432,
 176366841446208,
 205761315020576,
 308641972530864,
 411522630041152,
 617283945061728,
 1234567890123456]
In [23]:
# หาตัวประกอบเลข 1 - 100

for x in range(1,101):
    print(x,find_factors_2(x))
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]
In [ ]: