BaekJoon 1124번: 언더프라임, 에라토스테네스의 체 + 소인수 분해

이번에는 백준 1124번 언더프라임 문제에 대해 정리해 보려고 합니다. 언더프라임이란 소인수분해를 했을 때 인수의 개수가 소수인 수를 지칭하는 단어이고, 주어진 범위 내의 언더프라임의 개수를 구하는 문제이기 때문에, 저는 에라토스테네스의 체 개념을 이용해 소수들을 구한 후 소인수 분해 알고리즘을 통해 인수의 개수를 파악하는 방식으로 구현했습니다. 문제 링크: https://www.acmicpc.net/problem/1124 1124번: 언더프라임 1124번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 검색 언더프라임 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 3300 1229 934 39.560% 문제 자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. ...

원문링크 : BaekJoon 1124번: 언더프라임, 에라토스테네스의 체 + 소인수 분해