[BOJ / 백준] 2247 실질적 약수 (G5 / 수학) - Python

링크

https://www.acmicpc.net/problem/2247

 

 

 

 

문제 해석

SOD(n) : 1과 n을 제외한 모든 약수

CSOD(n) : 1부터 n까지 모든 SOD(i)의 합

 

 

 

입력 

n : 찾고자 하는 숫자

 

 

출력

CSOD(n)

 

 

 

 

풀이 & 코드 해석

문제 내용은 약수를 모두 찾아서 더해주는 심플하고 간단합니다.

 

단 n의 범위가 200,000,000 이기 때문에 매 숫자에 대한 약수를 구하는 것은 시간초과가 발생할 것입니다.

 

 

 

따라서 한 번에 하나의 값만 보는 것이 아니라 팩토리얼 나누기에서 했던 방식처럼 for문을 통해 반복을 진행하면서, 

 

현재 반복 중인 i라는 숫자로 나누어 떨어지는(약수로 가지는) 숫자가 몇 개인지를 세는 방식으로 구현하였습니다.

 

 

※ 팩토리얼 나누기 해석

https://angelplayer.tistory.com/563

[BOJ / 백준] 15996 팩토리얼 나누기 (S3^ / 수학) - Python

 

 

 

추가적으로 i의 범위는 전체 숫자 범위의 반을 초과하지 않습니다.

 

예를 들어 100까지 숫자를 구하고자 할 때 51을 약수를 가지는 숫자는 존재하지 않습니다.

 

따라서 반복문의 범위를 좁혀주면 시간 초과가 나는 것을 막을 수 있습니다.

 

 

 

 

코드

n = int(input())

ans = 0

for i in range(2, (n // 2) + 1):
    ans += ((n // i) - 1) * i

print(ans % 1000000)

 

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java