[Algorithm] 약수구하기/유클리드호제법으로 최대공약수 최소공배수 구하기

📌 개인적인 공간으로 공부를 기록하고 복습하기 위해 사용하는 블로그입니다.
정확하지 않은 정보가 있을 수 있으니 참고바랍니다 :😸
[틀린 내용은 댓글로 남겨주시면 복받으실거에요]

약수 구하기

 int n = 100;
        List<Integer> list = new ArrayList<>();
        for(int i = 1; i < (int) Math.sqrt(n); i++ ) {
            if (n % i == 0) {
                list.add(i); 
                
                // 약수 중 작은 수 저장 , 만약 100의 약수가 1과 100이라면 약수 1,
                
                if(n / i != i ) list.add(n / i); 
                
                //약수 중 큰 수 저장, 여기서는 100이 저장된다.
            }
        }

끝나고 나면 [ 1, 100, 2, 50, 4, 35, 5, 20 ,10 ] 으로 저장되어있어서 정렬이 필요할 경우 정렬 해주어야 한다.

• 정렬방법 1 : stream 사용하여 list로 반환

    list.stream().sorted().collect(Collectors.toList());
  

  만약 정렬 후 배열로 변경하고 싶을 때는 아래와 같이 사용 가능

    list.stream().sorted().mapToInt(i->i).toArray();
  

• 정렬방법 2

    Collections.sort(list);
  

유클리드 호제법

유클리드 호제법을 이용해서 최대공약수 , 최소공배수 구하기.

O(logN)의 시간복잡도로 두 자연수의 최대공약수를 구할 수 있는 알고리즘.

1. 최대공약수 알고리즘
   • 두 수 a와 b (a > b)가 주어졌을 때, a를 b로 나눈 나머지를 r
   • 이제 a와 b의 최대 공약수는 b와 r의 최대 공약수와 같습니다.
   • 이 과정을 r이 0이 될 때까지 반복합니다. r이 0이 되면, 그 때의 b가 a와 b의 최대 공약수이다.

    public int gcd (int a, int b) {
               
            if (b == 0) {
                return a;            
            }       
            return gcd(b, a % b);
        }
   

2. 최소공배수 LCM

   = 두 자연수의 곱 / 최대 공약수 ( LCM = a x b / GCD )

Algorithm 카테고리 내 다른 글 보러가기