약수 구하기
-
효욜적인 약수 개수 구하기 알고리즘 :: 마이구미알고리즘 2017. 2. 9. 18:06
이번 글은 약수를 구하는 알고리즘을 다뤄본다.약수 구하는 방법은 어렵지 않다.하지만 조금만 응용된 약수 관련 문제라면 순수한 방법으로는 시간이 너무 오래걸린다.더 효율적인 방법을 알아볼 것이다. 약수(約數, divisor)는 어떤 수를 나누었을 때 나머지가 0인 수를 말하며, 배수 관계와 서로 반대되는 개념이다. 약수는 보통 정수에 대해 정의되지만, 일반화하여 정역에 대해 정의하기도 한다. 관련 문제를 보자. (약수 문제)기본적인 문제로써, 주어진 수(N)의 약수의 개수를 구하는 문제이다.가장 순수한 방법으로는 1부터 N까지 N의 나머지를 구해 0이라면 약수라고 판단한다. int n = sc.nextInt(); int cnt = 0; for(int i = 1; i