C++ - (백준) 17425번 약수의 합

0. 문제

www.acmicpc.net/problem/17425

17425번: 약수의 합

1. 문제 해석

- 1~1000000 사이 숫자 중 N을 입력 받음

- 1부터 N까지 각 숫자의 약수들 합한것을 다 더한 것을 구함

 

2. 알아야할 것

2-1. 시간초과를 고려해야함

-> N을 입력받을때마다 1부터 N까지 각 숫자들의 약수를 구하고 다 더한 총 합을 구하면 시간이 초과됨

# 알고리즘 오류는 없지만 시간초과

#include <iostream>

int T;
int N;
int ans;


int main(){
    scanf("%d",&T);
    for(int t=0; t<T; t++){
        scanf("%d",&N);
        ans=0;
        
        for(int j=1; j<=N; j++){
            for(int i=1; i<=j; i++){
                if(j%i==0){
                    ans+=i;
                }
            }
            
        }
        printf("%d\n",ans);
    }

}

 

*N이 어떤 숫자이든 간에 미리 구해 놓은 답을 꺼내서 출력할 수 있게 하면 시간이 더 적게 걸림*

-> 배열에 N이 1~1000000 사이 값일 때 답은 뭐가 되는지 계산해서 미리 넣어둠