BOJ 21919번: 소수 최소 공배수

문제

행복이는 길이가 $N$인 수열 $A$에서 소수들을 골라 최소공배수를 구해보려고 한다.

행복이를 도와 이를 계산해주자.

입력

첫째 줄에 수열 $A$의 길이 $N$이 주어진다. $(1 \le N \le 10,000)$ 

그 다음줄에는 수열 $A$의 원소 $A_{i}$가 공백으로 구분되어 주어진다. $(2 \le A_{i} \le 1,000,000)$ 

답이 263 미만인 입력만 주어진다.

출력

첫째 줄에 소수들의 최소공배수를 출력한다.

만약 소수가 없는 경우는 -1을 출력한다.

---

위 문제를 풀기 위해선 에라토스테네스의 체에 대한 지식이 필요하다.

⭕️ 풀이 코드 - 성공

#include <stdio.h>
int prime[1000001];

int main() {
	int n, same = 0, count = 0;
    long long mul = 1;
    int arr[10001] = {0};
    scanf("%d", &n);
    
    for(int i=0; i<n; i++) { // 수열 입력 받기
        scanf("%d", &arr[i]);
    }
    
    for(int i=2; i<=1000000; i++) { // 에라토스테네스 체
        if(prime[i] == 0) {
            for(int j=2; j*i<=1000000; j++) {
                prime[j*i] = 1; // 합성수 체크  
            }
        }
    }
    
    for(int i=0; i<n; i++) {
        if(prime[arr[i]] == 0) { // 소수일 때
            count++;
            
            for(int j=0; j<i; j++) { // 중복 검사
                if(arr[j] == arr[i]) {
                    same = 1;
                    break;
                }
            }
            
            if(same == 0) { mul *= arr[i]; }
        }
    }
    if(count != 0) { printf("%lld", mul); }
    else { printf("-1"); }
    
    return 0;
}

❌ 풀이 코드 - 실패

❗️실패 원인: 소수가 중복되어 나오는 경우를 고려하지 못했다.

#include <stdio.h>
int prime[1000001];

int main() {
	int n, count = 0;
    long long mul = 1;
    int arr[10001] = {0};
    scanf("%d", &n);
    
    for(int i=0; i<n; i++) { // 수열 입력 받기
        scanf("%d", &arr[i]);
    }
    
    for(int i=2; i<=1000000; i++) { // 합성수 걸러내는 반복문
        if(prime[i] == 0) {
            for(int j=2; j*i<=1000000; j++) {
                prime[j*i] = 1; // 합성수 체크  
            }
        }
    }
    
    for(int i=0; i<n; i++) {
        if(prime[arr[i]] == 0) { // 소수일 때
            mul *= arr[i];
            count++;
        }
    }
    if(count != 0) { printf("%lld", mul); }
    else { printf("-1"); }
    
    return 0;
}