약수의 개수 구하기

#include <iostream>
int arr[50001];

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main() {
	
	//freopen("input.txt.txt", "rt", stdin);
	int n;
	scanf("%d", &n);
	
	
	for(int i=1 ; i <= n; i++){
		for(int j=i; j<=n; j=j+i){
			arr[j]++;
		}
	}
	for(int i =1; i <=n; i++){
		printf("%d ", arr[i]);
	}
	
	
	return 0;
	

}

약수의 개수 구하기

보통 약수의 개수를 구하려면

N^2의 시간복잡도를 이용해서 구하는게 먼저 생각나는데,

어떤 문제에서는 시간초과가 될 수 있다.

 

 

예를 들어 보통

10의 약수를 구하려면

(x%10==0)

x에 숫자를 다 대입해본다. 

 

대신에

더 빠른 시간으로 구하기 위해서는

위의 코드처럼 해당 수의 약수를 구해주는 게 아니라

어떤 수 i의 배수를 돌면서 약수의 개수를 더해준다.