프로젝트 오일러 문제 - Problem 3

문제)

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

What is the largest prime factor of the number 600851475143 ?

 

Sol.)

소인수(정확한 표현인가?)를 구하는 문제이다.

확실한 방법은 600851475143을 1부터 600851475143의 중간인 300425737571 까지 나눠보는 것이다.

그런데 어렴풋이 기억나는 방법으로는

 = 약 775146 까지 나눠서 떨어지는 수 까지가 소인수이고 그 이후의 숫자들은 소인수가 아님을 보증(guarantee)한다는 내용을 어디선가 들은 것 같다.

 

 

그걸 토대로 해본다면, (시간이 많이 걸렸다. 수업 중간중간 쉬는 시간에 푸느라..)

 

...................

 

 

import java.math.*;
import java.util.*;

class ProjectEuler{
 public static void main(String[] args){
  int i=1;
  BigInteger bi = new BigInteger("600851475143");
  HashSet arr = new HashSet();
  long ln = bi.longValue();

  for(i=1; i<Math.sqrt(ln); i++){
   if(ln%i==0){
    arr.add(i);
   }
   for(int j=2; j<Math.sqrt(i); j++){
    if(i%j==0){
     arr.remove(i);
    }
   }
   
  }
  
  System.out.println(arr);

  
 }
}

 

 

결과는 순서없이 출력되는 소인수들이 나오는데 가장 큰 수가 6857이다.

 

맨 처음에는 ArrayList로 작업했는데 중복을 허용하니 remove() 메소드를 사용할 때 인덱스값으로만 접근하여 삭제가 가능해서 HashMap으로 바꿔서 작업했다. HashMap은 중복을 허용하지 않으니, remove()메소드를 value 값으로 접근하여 삭제가 가능하다.

 

그런데 실행시간이 상당히 길다. (5초나 걸리네...)

 

어떻게 개선하면 좋을 지 생각해보고, 자료 찾아보고 다시 코딩해봐야겠다. (어떤 사람들은 ln / i 같은 식으로 연산 수를 급격히 줄이던데 난 그렇게 하니까 답이 안 나오더라... 1471이 젤 큰 것으로 나옴.)

 

 

------ 속도 개선한 코드 ------

import java.math.*;
import java.util.*;

class ProjectEuler{
 public static void main(String[] args){
  int i=1;
  BigInteger bi = new BigInteger("600851475143");
  HashSet arr = new HashSet();
  long ln = bi.longValue();

  for(i=1; i<Math.sqrt(ln); i+=2){        //어차피 소인수는 소수이니, 2를 제외한 모든 소수는 홀수이니까 굳이 짝수로

나눌 필요가 없어서 2씩 증가로 바꿨더니 5초 걸리던 것이 2~3초만에 결과가 나왔다.

   if(ln%i==0){
    arr.add(i);
   }
   for(int j=2; j<Math.sqrt(i); j++){
    if(i%j==0){
     arr.remove(i);
    }
   }
  }
  System.out.println(arr);
 }
}