[자바 알고리즘] 모두의 약수 (제한시간 1초)

광고 클릭은 개발자(저) 에게 큰 힘이 됩니다!!'ㅁ'

 

| 문제

자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하 세요. 만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4 개) 와 같이 각 숫자의 약수의 개수가 구해집니다. 출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다. 1 2 2 3 2 4 2 4 와 같이 출력한다.

 

| 입력설명

자연수 N(5<=N<=50,000)가 주어진다.

 

| 출력설명

1부터 N까지 약수의 개수를 순서대로 출력한다.

 

| 입력 예제

8

 

| 출력 예제

1 2 2 3 2 4 2 4

 

| 풀이

 

-- 첫번째

최대 값인 50000을 입력할 경우 2중 for문 안에서 i = 1 ,j = 1 , i =2 , j = 1,2 , i = 3, j = 1,2,3 이런식으로 n의 제곱으로 반복하게 된다.

for문

import java.util.Scanner;

public class Test9 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, i, j, cnt;
        n = sc.nextInt();
        for(i=1; i<= n; i++){
            cnt=0;
            for(j=1;j<=i;j++){
                if(i%j==0)cnt++;
            }
            System.out.printf("%d ",cnt);
        }
    }
}

 

cnt 배열을 전역으로 초기화 합니다. j= j+i로 증가

n 이 8이면 i는 1부터 시작을 한다 1은 모든 값의 약수 이므로 8개의 index에 1의 값이 저장

  1    2    3     4    5    6    7     8  

1

1

1

1

1

1

1

1

2를 약수로 가지는 값은 2의 배수이므로 2의 배수 index의 값을 증가

1

2

1

2

1

2

1

2

3을 약수로 가진 값

1

2

2

2

1

3

1

2

cnt배열에 값을 담아주면 이전의 n의 제곱으로 반복하던걸 줄여줄 수 있습니다.

import java.util.Scanner;

public class Test9 {
    static int[] cnt = new int[50001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, i, j;
        n = sc.nextInt();
        for(i=1; i<=n; i++){
            for(j=i; j<=n; j=j+i){
                cnt[j]++;
            }
        }
        for(i=1; i<=n; i++){
            System.out.printf("%d ", cnt[i]);
        }
    }
}

결과