[1주차 - 4] LCM(1, 2, ..., n)

[Jewan1120]

문제

• 문제 사이트: 백준
• 문제 이름: LCM(1, 2, ..., n)
• 문제 번호: 11690

문제 풀이 템플릿

### 시간복잡도 생각해보기
- 

### 풀이 아이디어
- 

### 의사코드
- 

[yereumi]

시간복잡도 생각해보기

• O(nlogn) n 이하의 소수 구하기 $\rightarrow$ O(nlogn) 소수의 최대 거듭제곱 구하기 $\rightarrow$ O(n) 최소공배수 갱신 $\rightarrow$ O(1) $\rightarrow$ O(nlogn)

풀이 아이디어

• n 이하의 모든 소수를 primes에 저장한다.
• primes를 순회하며 n이하의 범위에서 해당 소수의 최대 거듭제곱을 구한 후 lcm에 곱해준다.
  • lcm에 소수의 최대 거듭제곱을 곱하는 과정에서 long의 범위를 넘어갈 수 있으니 문제 조건의 $$2^{32}$$로 나눈 나머지를 곱해준다.
  • 매 순회할 때마다 long의 범위를 넘어가지 않도록 lcm에 $$2^{32}$$를 나눠준다.

의사코드

• 생략

[yeo-li]

시간복잡도 생각해보기

• 에라토스테네스의 체로 소수 마킹하기 → O(n^0.5*logn)
• 소수 p에 대한 n의 거듭제곱 구하기 → n*O(logn)
• 최종 시간 복잡도 → O(n*logn)

풀이 아이디어

• 1부터 n 사이에 있는 소수를 구한 뒤 각 소수마다 n을 넘지 않을때까지 곱해주어 소수 p의 거듭제곱을 구함
• 각 소수들의 거듭제곱을 곱해줄 때 마다 2^32로 모듈러 연산을 해주어 숫자 Long의 범위를 넘지 않도록 구현

의사코드

• 생략

[rladmstn]

시간복잡도 생각해보기

• n (2 ≤ n ≤ 10^8)
• 소수 목록 구하기 : O(NlogN)
• 최소공배수 계산 : n 이하 소수 개수 p개에 대해 O(plogN)?
• 최종 : O(NlogN)

풀이 아이디어

• n 이하의 모든 소수 구하기
• 소수 목록을 순회하며 n 이하일 때까지만 거듭 제곱 진행
• 거듭 제곱 했던 값을 result에 곱함
• 2^23으로 나머지 구해 값이 너무 커지지 않도록 함

의사코드

• 생략

[chaerish]

시간복잡도 생각해보기

• 소수 구하는 getPrime() 함수: O(NlogN)
• N을 돌면서 i^k가 N을 넘지 않도록 거듭 제곱을 계산한다: O(NlogN) -> O(NlogN)

풀이 아이디어

• N까지 소수인 수를 구하고,
• 소수인 것들의 거듭제곱을 N보다 커지기 전까지 구한다.
• 그 값을 divide값으로 나누고, result에 곱해준다.

의사코드

• 생략

  틀린코드 (왜틀렸는지모르겟다..)

  
  mport java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;

public class BJ11 { static long divide = 4294967296L; // 2^32 static long [] arr; static boolean [] barr; static int N;

public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());

    long result = 1; 
    arr= new long [N+1];
    barr = new boolean[N+1];
    getPrime();

    for(int i=2; i<=N;i++) {
        if(result%i == 0) {
            continue;
        }
        result= (result * arr[i]) % divide;
    }

    System.out.println(result); 
}
private static void getPrime() {
    for(int i=2; i<=N; i++) {
        if(barr[i]) {
            continue;
        }
        for(int j=i;j<=N;j+=i) {
            arr[j] = i;
            barr[j] = true;
        }
    }

}

}