[2809] 약수

문제

한 개의 정수를 입력받아 입력받은 정수의 약수를 모두 출력하는 프로그램을 작성하시오.

입력

정수 N이 주어진다. (2 ≤ N ≤ 21억)

출력

N의 약수를 작은 수부터 차례로 모두 출력한다.

---

예제 입력 

24

 

예제 출력

1 2 3 4 6 8 12 24

---

처리조건

 

약수 : 어떤 수를 나누어 떨어지게 하는 수 

- a * b = c 일 경우 a 와 b는 c의 약수가 되며, 어떤 수 i가 N의 약수일 경우 N % i = 0 이다.

 

- 1은 모든 수의 약수이며 자기 자신 또한 약수가 된다. 따라서 1보다 큰 자연수라면 반드시 2개 이상의 약수를 가지게 된다.

- a * b = c 일때 a가 작은수인 경우 b = c /a 로 접근이 가능하며, a * a <= c 인 경우 c의 제곱근까지만 반복문을 실행하면 원하는 값을 얻을 수 있다.

 

<입력의 설계>

- 입력받을 변수 n, 약수를 저장할 배열 arr, arr배열에 순서대로 약수를 저장할 cnt 를 선언한다. 

- cnt 는 0으로 초기화 하여 준다. 

- scanf 함수를 이용해 n을 입력받는다.

int n;
int cnt = 0;
int arr[10000] = {0};

scanf("%d", &n);

 

 

출력형식

<math.h> 헤더 사용 

 

<출력의 설계>

(1) N의 제곱근을 계산하고, 정수로 변환하여 sq에 저장한다.

* 약수는 각 숫자와 대응하기 때문에 짝짓는 원리를 활용하면 쉽게 약수를 찾을 수 있다. 

int sq = (int)sqrt(N);

 

(2) 1부터 sq까지 반복문을 활용해 약수를 찾아 출력하고, arr배열에 저장한다.

* 큰수부터 저장됨 

if(N % i == 0)
{
	printf("%d ", i);
	arr[cnt++] = N / i;
}

 

 

(3) 짝지어서 2번씩 저장하므로 중복으로 저장된 약수의 경우 제거 해준다. 

if(sq * sq == N) cnt--;

 

(4) 차례로 출력하여준다.

for (int i = cnt; i > 0; i--) {
    printf("%d ", arr[i - 1]);
}

 

설계특징

- N의 크기가 최대 21억 이므로 연산이 길어져 일어나는 시간초과를 주의하여야 한다.

- 연산이 1억 이하라면 안정적으로 1초 이내에 답이 나올 수 있다.

 

제출답변

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int main()
{
	int n;
	int cnt = 0;
	int arr[10000] = { 0 };

	scanf("%d", &n);

	int sq = (int)sqrt(n);
	for (int i = 1; i <= sq; i++)
	{
		if (n % i == 0)
		{
			printf("%d ", i);
			arr[cnt++] = n / i;
		}
	}

	if (sq * sq == n) cnt--;
	for (int i = cnt; i > 0; i--) {
		printf("%d ", arr[i - 1]);
	}

	return 0;
}