Lv.1mathnumber-theorysieve
약수의 개수 구하기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
양의 정수 배열 nums가 주어집니다. 각 nums[i]의 약수의 개수를 구해 같은 순서로 배열에 담아 반환하세요.
약수는 나누어떨어지게 하는 양의 정수입니다. 예를 들어 12의 약수는 1, 2, 3, 4, 6, 12로 6개입니다.
입출력 예
| nums | result |
|---|---|
[1, 6, 12] | [1, 4, 6] |
[7, 36, 100] | [2, 9, 9] |
[5000000] | [56] |
입출력 예 설명
예 1 — 1의 약수는 1 하나, 6의 약수는 1, 2, 3, 6입니다.
예 2 — 7은 소수이므로 약수가 2개입니다. , 는 모두 약수가 개입니다.
예 3 — 이므로 약수는 개입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(nums: int[]) → int[]
제한 사항
-
nums.length -
nums[i]
기대 복잡도
- 시간
- O(M log log M + Q log M)
- 공간
- O(M)
입출력 예
| nums | 기대 출력 |
|---|---|
[1,6,12] | [1,4,6] |
[7,36,100] | [2,9,9] |
[5000000] | [56] |
힌트
힌트
로 소인수분해되면 약수의 개수는 입니다. 각 소인수를 0번부터 번까지 고를 수 있기 때문입니다.
값이 많으므로 소인수분해를 빠르게 해야 합니다. 에라토스테네스의 체를 변형해 각 수의 가장 작은 소인수(spf[x])를 미리 구해 두세요. 그러면 x를 spf[x]로 계속 나누는 것만으로 소인수분해가 되고, 나누는 횟수는 이하입니다.
복잡도 목표
값마다 까지 나눠 보면 값 하나에 2천 번이 넘어, 20만 개에서는 효율성 테스트에서 시간 초과가 납니다. 체를 한 번 만드는 과 값마다 이 필요합니다(은 최댓값).
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 248 ms | 추정 |
| C++ (GCC, gnu++23) | 248 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1490 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1496 ms | 추정 |
| C# 14 (.NET 10) | 1496 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 3 | 판정만 |