#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
int n, i, j, cnt = 0;
int arr[50001];
scanf("%d",&n);
for(i = 1; i <= n; i++){
for(j = i; j <= n; j = j+i){ //i를 약수로 갖는 숫자들은 i의 배수(i만큼 증가)이다.
arr[j]++;//i를 약수로 갖는 숫자 j번째 인덱스에 1씩 count한다.
}
}
for(i = 1; i <= n; i++){
printf("%d",arr[i]);
}
return 0;
}
성찰
- 역으로 생각하는 방법을 적용한다 : 8의 약수는 무엇일까? => 8을 약수로 갖는 수는 무엇일까? == 8의 배수는 무엇일까?
- 1~i를 약수로 갖는 수를 모두 count한다.
- i를 약수로 갖는 수는 i의 배수이다.(2를 약수로 갖는 수는 2,4,6,8..)
'기타등등 > 알고리즘 기록' 카테고리의 다른 글
[C++] 숫자의 총 개수(Large) (0) | 2021.06.18 |
---|---|
[C++] 자릿수의 합 & 숫자의 총 개수 (0) | 2021.06.18 |
[C++] 올바른 괄호 (0) | 2021.06.16 |
[C++] 영어 단어 복구(공백제거, 대소문자) (0) | 2021.06.16 |
[C++] 나이 계산(문자열 컨트롤) (0) | 2021.06.16 |