home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Java

หาตัวหารเฉพาะมากที่สุด (Largest Prime Factor) ใน Java

Largest Prime Factor

หาตัวหารเฉพาะ (Prime Factor) ที่มีค่ามากที่สุดของจำนวนเต็มบวก

ตัวอย่างโค้ด

import java.io.*; 
import java.util.*; 

public class Demo { 
    static long maxPrimeFactors(long n) { 
        long maxPrime = -1; 
        
        // แยกตัวประกอบ 2 ออกก่อน (ทำให้ n คี่)
        while (n % 2 == 0) { 
            maxPrime = 2; 
            n >>= 1; // n /= 2 (bit shift เร็วกว่า)
        } 
        
        // ตรวจสอบตัวหารคี่ จาก 3 ถึง sqrt(n)
        for (long i = 3; i <= Math.sqrt(n); i += 2) { 
            while (n % i == 0) { 
                maxPrime = i; 
                n /= i; 
            } 
        } 
        
        // ถ้า n เหลือ > 2 แสดงว่า n เองเป็นเฉพาะ (และมากกว่าตัวหารที่เจอ)
        if (n > 2) 
            maxPrime = n; 
        
        return maxPrime; 
    } 
    
    public static void main(String[] args) { 
        long n1 = 148592; 
        System.out.println("Largest prime factor of " + n1 + ": " + maxPrimeFactors(n1)); 
        
        long n2 = 890654; 
        System.out.println("Largest prime factor of " + n2 + ": " + maxPrimeFactors(n2)); 
    } 
}

ผลลัพธ์

Largest prime factor of 148592: 251
Largest prime factor of 890654: 4591

คำอธิบายอัลกอริทึม

  1. แยก 2: หาร 2 ซ้ำจนไม่หารลดลง → n กลายเป็นคี่
  2. วนลูปคี่: ตรวจสอบ i = 3, 5, 7... จนถึง √n (เพราะถ้ามีตัวหาร > √n จะมีคู่ที่ < √n)
  3. หารซ้ำ: while (n % i == 0) แยกตัวประกอบ i ออกหมด
  4. เหลือ n > 2: n ที่เหลือเป็น prime เอง (และมากกว่าทุกตัวที่เจอ)

Trace (n = 148592)

148592 ÷ 2 = 74296 (maxPrime=2)
74296 ÷ 2 = 37148
37148 ÷ 2 = 18574
18574 ÷ 2 = 9287 (maxPrime=2, n=9287 odd)

i=3: 9287%3≠0
i=5: 9287%5≠0
...
i=37: 9287÷37=251 (maxPrime=37)
251÷37≠0
i=39, 41... √251≈15.8 -> loop ends (i starts at 37, next 39 > 15.8? Wait...)
Actually: after dividing by 37, n=251. sqrt(251)≈15.8. But i=37 > 15.8, loop condition fails.
Then n=251 > 2, so maxPrime = 251. ✓

การปรับปรุงประสิทธิภาพ

// 1. Pre-compute sqrt
for (long i = 3, max = (long)Math.sqrt(n); i <= max; i += 2) { ... }

// 2. Wheel factorization (skip multiples of 3, 5)
for (long i = 3; i * i <= n; i += 2) { ... }

// 3. Pollard's Rho สำหรับเลขใหญ่มาก (64-bit+)

Java Built-in (ไม่มีโดยตรง)

Java ไม่มี built-in สำหรับ prime factorization ต้อง implement เอง หรือใช้ไลบรารีเช่น Apache Commons Math

การประยุกต์ใช้

  • Cryptography (RSA - ความยากในการแยกตัวประกอบ)
  • Number Theory research
  • Mathematical puzzles (Project Euler Problem 3)
  • Hash table sizing (prime numbers)