การหารเชิงทดลอง

การหารเชิงทดลอง () เป็นขั้นตอนวิธีที่ทำความเข้าใจได้ง่าย เนื่องจากเป็นขั้นตอนวิธีที่ใช้วิธีการแบบบรู๊ทฟอร์ซ (brute-force) เพื่อช่วยในการแยกตัวประกอบของจำนวนเต็ม n โดยตรวจสอบว่ามีจำนวนเฉพาะใดๆที่มากกว่า 1 แต่น้อยกว่า n ที่สามารถหาร n ได้ลงตัว โดยวิธีนี้มักใช้กับการแยกตัวประกอบของจำนวนเต็มค่าน้อยๆ เนื่องจากประสิทธิภาพเชิงเวลาค่อนข้างช้า

 คำอธิบาย 
การหารเชิงทดลองนั้น ใช้หลักของการหาขอบเขตล่างและขอบเขตบน(lower bound&upper bound)เข้ามาช่วย กำหนดให้ จำนวนเต็ม n= s×t และ s ≤ t เราจะทำการตรวจสอบว่ามี s | n (หมายถึง s หาร n ได้ลงตัว) สำหรับจำนวน s = {2, ..., √n} โดยขอบเขตบน คือ s ≤ √n นั้น มีทฤษฎีดังนี้

ทฤษฎี : ตัวประกอบเฉพาะของจำนวนเต็มใดๆ จะต้องมีค่าน้อยกว่าหรือเท่ากับรากที่สองของจำนวนเต็มนั้นๆ

บทพิสูจน์ : สมมุติให้ s > √n ดังนั้น t ≥ s > √n เป็นผลให้ n < s×t ทำให้ขัดแย้งกับข้อเท็จจริง n = s×t เพราะฉะนั้น s ≤ N

ตัวอย่างที่1 : ให้จำนวนเต็มบวก n มีค่าเท่ากับ 7399 สามารถแสดงขั้นตอนวิธีการทำได้ดังนี้

 ทดลองนำจำนวนเฉพาะ 2,3,5 มาหารพบว่า ไม่ใช่ตัวประกอบของ n (หาร n ไม่ลงตัว)
 ทดลองนำจำนวนเฉพาะ 7 พบว่า 7 เป็นตัวประกอบของ n โดย n/7 = 1057
 จากนั้นลองนำ 7 มาหารซ้ำอีกครั้ง พบว่า 7 เป็นตัวประกอบของ 1057 ทำให้ 1057/7 = 151
 ลองนำ 7 มาหารอีกครั้ง พบว่าหารไม่ลงตัว ดังนั้น 7 ไม่ใช่ตัวประกอบของ 151
 เลื่อนไปที่จำนวนเฉพาะตัวถัดไปคือ 11 พบว่าหารไม่ลงตัว ดังนั้น 11 ไม่ใช่ตัวประกอบของ 151
 เมื่อเลื่อนไปที่จำนวนเฉพาะตัวถัดไปจาก 11 คือ 13 จะพบว่าไม่สามารถคิดต่อได้ เนื่องจาก 13 มีค่ามากกว่ารากที่สองของ 151 ซึ่งคือ 12.288 
 เพราะฉะนั้น ตัวประกอบของ 7399 คือ 7×7×151

ตัวอย่างที่2 : ให้จำนวนเต็มบวก n มีค่าเท่ากับ 491 สามารถแสดงขั้นตอนวิธีการทำได้ดังนี้
 ทดลองนำจำนวนเฉพาะ 2, 3,5...,19พบว่าไม่ใช่ตัวประกอบของn (หาร n ไม่ลงตัว)
 เมื่อเลื่อนไปที่จำนวนเฉพาะตัวถัดไปจาก 19 คือ 23 จะพบว่าไม่สามารถคิดต่อได้ เนื่องจาก 23 มีค่ามากกว่ารากที่สองของ 491 ซึ่งคือ 22.158
 เพราะฉะนั้น 491 ไม่มีจำนวนเฉพาะใดๆเป็นตัวประกอบ 491 จึงเป็นจำนวนเฉพาะ

 รหัสเทียม 
def trial_division(n):
    """Return a list of the prime factors for a natural number."""
    if n == 1: return [1]
    primes = prime_sieve(int(n**0.5) + 1)
    prime_factors = []

    for p in primes:
        if p*p > n: break
        while n % p == 0:
            prime_factors.append(p)
            n //= p
    if n > 1: prime_factors.append(n)

วิสุดา  

    return prime_factors

 ประสิทธิภาพการทำงาน 
ประสิทธิภาพเชิงเวลาของการหารเชิงทดลอง ในกรณีที่แย่ที่สุด คือ จำนวนเต็มที่ต้องการทดลองเป็นจำนวนเฉพาะ ในกรณีนี้จะใช้จำนวนเฉพาะตั้งแต่ 2 ถึง √n โดยต้องทำเป็นจำนวน 2√n / ln n ครั้ง ทำให้มีประสิทธิภาพเชิงเวลาเป็น O(√n / log n)

การใช้การหารเชิงทดลองเป็นวิธีที่รวดเร็วสำหรับการแยกตัวประกอบของจำนวนเต็มที่มีตัวประกอบน้อยๆ เนื่องจาก มีจำนวนเต็ม 50% ที่มี 2 เป็นตัวประกอบ, 33% ที่มี 3 เป็นตัวประกอบ, 88% ที่มีจำนวนเต็มที่มีค่าน้อยกว่า 100 เป็นตัวประกอบ และ 92% ที่มีจำนวนเต็มที่มีค่าน้อยกว่า 1000 เป็นตัวประกอบ ดังนั้นจึงคุ้มค่าที่จะเริ่มหาตัวประกอบจากจำนวนเฉพาะดังขั้นตอนวิธีนี้

 การประยุกต์ใช้ 
การหารเชิงทดลองเป็นขั้นตอนวิธีที่ช่วยในการแยกตัวประกอบจำนวนเต็ม การหาตัวประกอบเฉพาะ และการหาตัวหารร่วมมาก

 ดูเพิ่ม 
ขั้นตอนวิธีที่เกี่ยวข้องกับการแยกตัวประกอบ อาทิ
 ขั้นตอนวิธีของชอร์
 ขั้นตอนวิธีโรห์ของพอลลาร์ด
ตะแกรงของเอราทอสเทนีส
 การแยกตัวประกอบแบบออยเลอร์

 อื่นๆ 
ตัวอย่างการทำหารหารเชิงทดลองด้วนภาษาคอมพิวเตอร์ต่างๆ

 ภาษาซี
 ภาษาจาวา

 อ้างอิง 
 .
 .

หมวดหมู่:ขั้นตอนวิธีการแยกตัวประกอบจำนวนเต็ม
หมวดหมู่:การทดสอบจำนวนเฉพาะ
หมวดหมู่:การหาร