13195的质数因子有5,7,13和29.
 
600851475143的最大质数因子是多少？


求高效思路，最好有代码

600851475143  这个数有点大...

我的这个代码只能求小范围的数的最大质因子...   

#include<stdio.h>
main()
{
    int i=2,k;
    printf("请输入一个数:");
    scanf("%d",&k);
    while(k!=1) 
    {
        while(k%i==0 )
        {
            if(k/i==1)
                printf("最大质因子为：%d\n",i);
            k=k/i;
        }
        i++;
    }
    return 0;
}

又是大数处理问题吗，据以前问题的回答是用数组模拟大数。具体没用过

5753023

用 __int64完全装的下，先取600851475143的平方根 s1 = 775146，再取 s1的平方根 s2 = 880，用数组存储所有不小于 s2的质数，把 s1递减

同时满足 被600..143整除 和 不被数组中任一质数整除的，就是结果了。应该是 6857

楼上的不是质数，5753023 = 6857 * 839

代码不复制了，不难，自己写写

貌似把 s2递增更快些


这个说法不对，需要把是s1 - s2全部判断，递减更快，一不小心就二了，额

[ 本帖最后由 azzbcc 于 2013-3-26 11:12 编辑 ]

呵，我用exce1分解不彻底啊

学习点，

引理：一个数n至多有一个大于sqrt(n)的质因子

所以把n从2到sqrt(n)全部全部试除一次，剩下一个数如果不等于1，那么他就是最大的质因子

如果为1的话，则试除过程中最后一个除过的数就是最大质因子