如何找到600851475143最大的主要因素？ [英] How to find the largest prime factor of 600851475143?

问题描述

#include <stdio.h>
main()
{
    long n=600851475143;
    int i,j,flag;
    for(i=2;i<=n/2;i++)
    {
        flag=1;
        if(n%i==0)//finds factors backwards
        {
            for(j=2;j<=(n/i)/2;j++)//checks if factor is prime
            {
                if((n/i)%j==0)
                    flag=0;
            }
            if(flag==1)
            {
                printf("%d\n",n/i);//displays largest prime factor and exits
                exit(0);
            }
        }    
    }
}

在code以上作品 N = 6008514751 。但是，它不工作 N = 600851475143 ，虽然这个数字仍然是该范围内的长 。结果
我能做些什么使它工作？

The code above works for n = 6008514751. However, it doesn't work for n = 600851475143, even though that number still is within the range of a long.
What can I do to make it work?

推荐答案

一个潜在的问题是， I 和Ĵ是 INT ，并可能溢出的大型 N （假设 INT 比窄长，它经常是）。

One potential problem is that i and j are int, and could overflow for large n (assuming int is narrower than long, which it often is).

另一个问题是，当n = 600851475143你的程序做了不少工作（最大的因素是6857）。这是不是不合理的期望它需要很长的时间才能完成。

Another issue is that for n=600,851,475,143 your program does quite a lot of work (the largest factor is 6857). It is not unreasonable to expect it to take a long time to complete.

这篇关于如何找到600851475143最大的主要因素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！