最大素因數

Largest prime factor

篩選法原理适用于本程式，但是不需要用數組來存儲篩選結果。

本程式參考歐拉函數寫成，是采用逐漸排除小素數因子最後得到最大素因數的方法。

/*
 * 最大素因數—Largest prime factor
 *
 * The prime factors of 13195 are 5, 7, 13 and 29.
 * What is the largest prime factor of the number 600851475143 ?
 *
 * 這個問題稱為"Prime Factorization"(分解質因數)，prime factor稱為質因子(或素因子)。
 * 素數也稱為質數，是隻能被1和自身整除的整數，不包括1。
 *
 * 本程式是參考歐拉函數寫成的。
 * 條件：n>=2
 *
 */

#include <stdio.h>

long maxfact(long n)
{
    long ret=2L, i;

    while(n%2 == 0)
        n /= 2;

    for(i=3; i*i<=n; i+=2) {
        if(n%i == 0) {
            ret = i;
            n /= i;
            while(n%i == 0)
                n /= i;
        }
    }
    return (n==1)?ret:n;
}

int main(void)
{
    printf("n=%ld maxfact=%ld\n", 32L, maxfact(32));

    printf("n=%ld maxfact=%ld\n", 9L, maxfact(9));

    printf("n=%ld maxfact=%ld\n", 13195L, maxfact(13195));

    printf("n=%ld maxfact=%ld\n", 600851475143L, maxfact(600851475143));

    return 0;
}      

關鍵代碼：

/* 最大素因數 */
long maxfact(long n)
{
    long ret=2L, i;

    while(n%2 == 0)
        n /= 2;

    for(i=3; i*i<=n; i+=2) {
        if(n%i == 0) {
            ret = i;
            n /= i;
            while(n%i == 0)
                n /= i;
        }
    }
    return (n==1)?ret:n;
}