我的欧拉工程之路_3

2023-01-31 01:01:10 工程 欧拉 之路

Largest prime factor

Problem 3

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

What is the largest prime factor of the number 600851475143 ?

最大的素数因数

问题 3

13195 的素数因数是 5, 7, 13 和 29.

那么数字 600851475143 最大的素数因数的多少?

public class Euler3
{
    //返回一个一维素数数组,长度为length
    public static int[] getPrimeArray(int length)
    {
        int[] prime =new int[length];
        prime[0]=2;
        for(int num=3,lengthTemp=1;lengthTemp!=length;num+=2)
        {
            int i;
            boolean primeFlag=true;
            for(i=3;i<=Math.sqrt(num);i+=2)
            {
                if(num%i==0)
                {
                    primeFlag=false;
                    break;
                }
            }
            if(primeFlag==true)
            {
                prime[lengthTemp]=num;
                lengthTemp++;
            }
        }
        System.out.println("已生成素数数组,长度为"+length+"最后一个元素为"+prime[length-1]);
        return prime;
    }
    public static void main(String[] args)
    {
        int length=1000,primeMax=2;
        long num=600851475143L;
        int[] prime=Euler3.getPrimeArray(length);
        for(int i=0;i<length && prime[i]<=num;i++)
        {
            while(num%prime[i]==0)
            {
                primeMax=prime[i];
                num/=prime[i];
            }
        }
        System.out.println("primeMax="+primeMax);
    }
}


相关文章