我的欧拉工程之路_3

• 2020 年 1 月 14 日
• 笔记

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