[백준 / BOJ] 1124 언더프라임

문제

출처 : https://www.acmicpc.net/problem/1124

1124번: 언더프라임

두 양의 정수 A,B가 주어졌을때, A,B사이의 언더프라임을 구하는 문제다.

여기서 언더프라임은 정수의 소인수분해의 결과로 나온 소수들의 길이가 소수인 수를 의미한다.

---

풀이

에라토스테네스 채를 이용해서 A,B사이의 모든 소수들을 구해놓은 후, A,B사이에 있는 임의의 정수 X가 언더프라임인지 확인하는 방식으로 푸는 문제다.

이 때, 시간이 애매할거 같아서, 연산을 빠르게 진행하기 위해 다음과 같은 알고리즘을 넣었다.

 

1. A,B사이에 있는 임의의 정수 X를 구한다.

2. 1번에서 구한 임의의 정수 X에 소수 1개를 곱한값은 다음과 같다.

-> 정수 X가 언더프라임 이라면 소수 1개를 곱한값은 언더프라임이 아니다.

-> 정수 X가 언더프라임이 아니라면, 소수 1개를 곱한값은 언더프라임이다.

 

따라서, 정수X에 대해 판별한 후, 소수 목록들을 차례로 곱해가며 언더프라임을 만들어주면된다.

 

주요 소스코드

void markUnderPrime(int num, int cnt){
    if(underPrimeVisited[num]) return;
    underPrimeVisited[num] = true;
    if(isPrime[cnt]) isUnderPrime[num] = 1;
    else isUnderPrime[num] = -1;
    for(int i = 0; i < primes.size(); i++){
        int nextNum = num * primes[i];
        if(nextNum > B) break;
        markUnderPrime(nextNum, cnt+1);
    }
}

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/1124%20언더프라임/main.cpp

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃