[백준] 21919번 소수 최소 공배수 / C++ Java

문제 : https://www.acmicpc.net/problem/21919

초기코드

#include<iostream>
using namespace std;

bool isPrime(int a) {
    if(a==1) {
        return false;
    }
    for(int i = 2; i < a; i++) {
        if(a % i == 0) {
            return false;
        }
    }
    return true;
}

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

long long lcd(long long a, long long b) {
    return a * b / gcd(a,b);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n,number;
    long long total = 1;
    cin >> n;
    for(long long i = 0; i < n; i++) {
        cin >> number;
        if(isPrime(number)) {
            total = lcd(total, number);
        }
    }
    if(total==1) {
        cout << -1 << "\n";
    }
    else{
        cout << total << endl;
    }
}

C++

#include<iostream>
#include<cmath>

using namespace std;

bool isPrime(long long a) { // 에라토스테네스의 체 사용
    if(a < 2) {
        return false;
    }
    for(int i = 2; i * i<= a; i++) {
        if(a % i == 0) {
            return false;
        }
    }
    return true;
}

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

long long lcd(long long a, long long b) {
    return a * b / gcd(a,b);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n,number;
    long long total = 1;
    cin >> n;
    for(long long i = 0; i < n; i++) {
        cin >> number;
        if(isPrime(number)) {
            total = lcd(total, number);
        }
    }
    if(total==1) {
        cout << -1 << "\n";
    }
    else{
        cout << total << endl;
    }
}

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private static boolean isPrime(int n) {
        if(n < 2) return false;
        for (int i = 2; i  * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        boolean[] bool = new boolean[1000001];

        long result = 1;

        String[] line = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(line[i]);
            if (isPrime(num) && !bool[num]) {
                result *= num;
                bool[num] = true;
            }
        }

        if (result == 1)
            System.out.println(-1);

        else
            System.out.println(result);
    }

}

문제풀이

• 초기코드에서 소수를 구하는 방식으로 제출했을 때, 시간초과 오류가 떴다. 따라서 모든 소수를 찾기 위해 소수를 찾는 것이 아닌 합성수를 찾아 제거하는 방식인 에라토스테네스의 체의 방식을 사용했다. 그리고 최대공약수와 최소공배수 함수를 정의했다. 메인문에서는 값을 입력받고, 소수 판별을 한 뒤 소수라면 바로 total과의 최소공배수를 구했다.

Comment

• int형이 아닌 long long형, 일반적인 소수 구하는 방법이 아닌 에라토스테네스의 체 방식 사용. 신경써야 할 부분이 여러가지인 문제이다.

참고블로그 : https://llee-chan.tistory.com/9