#!/usr/bin/env python
# coding: utf-8

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

# In[1]:


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

x = 100
for i in range(1,x+1):
    if x % i == 0:
        print(i)


# 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)


# 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)


# In[6]:


# เก็บตัวประกอบของ 12 ไว้ในตัวแปรลิสต์ชื่อ factors
# ใช้ len(factors) นับจำนวนตัวประกอบของ 12

factors = find_factors(12)
len(factors)


# In[7]:


# เราใช้คำสั่ง %time เพื่อจับเวลาการทำงานฟังก์ชั่นได้
get_ipython().run_line_magic('time', 'find_factors(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)


# In[9]:


# ทำความรู้จัก math.ceil() ที่ปัดเศษขึ้นไปเป็นจำนวนเต็ม

math.ceil(3.5)


# In[10]:


# ทำความรู้จัก math.floor() ที่ปัดเศษลงมาเป็นจำนวนเต็ม
math.floor(3.5)


# In[11]:


# การหารปกติด้วย / จะได้ผลลัพธ์เป็นเลขทศนิยม

12 / 3


# In[12]:


# การหารด้วย // จะได้ผลลัพธ์เป็นเลขจำนวนเต็ม เศษถูกทิ้งไป
12 // 3


# In[13]:


14 // 3


# 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)


# 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)


# 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)


# In[20]:


# ใช้ %time จับเวลาการทำงานหาตัวประกอบเลข 9 หลัก
# วีธีนี้หาตัวหารจาก 1 ถึง 123456789

get_ipython().run_line_magic('time', 'find_factors(123456789)')


# In[21]:


# ใช้ %time จับเวลาการทำงานหาตัวประกอบเลข 9 หลัก
# วีธีนี้หาตัวหารจาก 1 ถึง sqrt(123456789) หรือประมาณ 10,000
# เร็วกว่าวิธีด้านบนประมาณหลายพันถึงหมื่นเท่่า

get_ipython().run_line_magic('time', 'find_factors_2(123456789)')


# In[22]:


# ลองจับเวลาหาตัวประกอบเลข 16 หลัก
# ใช้เวลาไม่นาน
get_ipython().run_line_magic('time', 'find_factors_2(1234567890123456)')


# In[23]:


# หาตัวประกอบเลข 1 - 100

for x in range(1,101):
    print(x,find_factors_2(x))


# In[ ]: