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 
    
     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;}

参考链接：