项目Euler＃3永远使用Java [英] Project Euler #3 takes forever in Java

问题描述

项目Euler上的问题＃3是：

13195的素因子是5,7,13和29。

600851475143的最大素数因素是什么？

我的解决方案需要永远。我认为我得到了正确的实施;然而，当用大数字进行测试时，我无法看到结果。它永远运行。我想知道我的算法是否有问题：

  public class LargestPrimeFactor3 {
 
 public static void main （String [] args）{
 long start，end，totalTime; 
 long num = 600851475143L; 
 long pFactor = 0; 
 
 start = System.currentTimeMillis（）; 
 
 for（int i = 2; i< num; i ++）{
 if（isPrime（i））{
 if（num％i == 0）{
 pFactor = i; 
} 
} 
} 
 
 end = System.currentTimeMillis（）; 
 totalTime =结束 - 开始; 
 System.out.println（pFactor +Time：+ totalTime）; 
} 
 
 static boolean isPrime（long n）{
 
 for（int i = 2; i< n; i ++）{
 if（
 if（ n％i == 0）{
返回false; 
} 
} 
返回true; 
} 
} 
  

解决方案

虽然不是Java，我想你可能会发现以下内容。基本上，需要通过仅测试奇数除数和直到数字的平方根来减少迭代。这是一种蛮力方法，可以在C＃中提供即时结果。

 静态bool OddIsPrime（long oddvalue）//测试奇数> = 3 
 {
 //只测试奇数除数。 
 for（long i = 3; i< = Math.Sqrt（oddvalue）; i + = 2）
 {
 if（value％i == 0）
 return假; 
} 
返回true; 
} 
 
 static void Main（string [] args）
 {
 long max = 600851475143; //奇数值
 long maxFactor = 0; 
 
 //只测试MAX的奇数除数。将搜索限制在MAX的Square Root内。 
 for（long i = 3; i< = Math.Sqrt（max）; i + = 2）
 {
 if（max％i == 0）
 { 
 if（OddIsPrime（i））//我是奇数
 {
 maxFactor = i; 
} 
} 
} 
 Console.WriteLine（maxFactor.ToString（））; 
 Console.ReadLine（）; 
} 
  

Problem #3 on Project Euler is:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

My solution takes forever. I think I got the right implementation; however, when testing with the big number, I have not being able to see the results. It runs forever. I wonder if there's something wrong with my algorithm:

public class LargestPrimeFactor3 {

    public static void main(String[] args) {
        long start, end, totalTime;
        long num = 600851475143L;
        long pFactor = 0;

        start = System.currentTimeMillis();

        for(int i = 2; i < num; i++) {
            if(isPrime(i)) {                
                if(num % i == 0) {
                    pFactor = i;                        
                }
            }
        }

        end = System.currentTimeMillis();
        totalTime = end - start;
        System.out.println(pFactor + " Time: "+totalTime);
    }

    static boolean isPrime(long n) {

        for(int i = 2; i < n; i++) {
            if(n % i == 0) {
                return false;
            }
        }        
        return true;
    }     
}

解决方案

Although not in Java, I think you can probably make out the following. Basically, cutting down on the iterations by only testing odd divisors and up to the square root of a number is needed. Here is a brute force approach that gives an instant result in C#.

static bool OddIsPrime (long oddvalue)  // test an odd >= 3 
{
    // Only test odd divisors.
    for (long i = 3; i <= Math.Sqrt(oddvalue); i += 2)
    {
        if (value % i == 0)
            return false;
    }
    return true;
}

static void Main(string[] args)
{
    long max = 600851475143;   // an odd value
    long maxFactor = 0;

    // Only test odd divisors of MAX. Limit search to Square Root of MAX.
    for (long i = 3; i <= Math.Sqrt(max); i += 2)
    {
        if (max % i == 0)
        {
            if (OddIsPrime(i))  // i is odd
            {
                maxFactor = i;
            }
        }
    }
    Console.WriteLine(maxFactor.ToString());
    Console.ReadLine();
}

这篇关于项目Euler＃3永远使用Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！