컨텐츠 바로가기

약수 고속검색 알고리즘

http://irakla.egloos.com/6291315

일반적으로, 아무런 요구사항도 없이 특정한 수의 약수를 모두 찾아내는 프로그램을 짜라고하면, 보통 다음과 같은 코드가 나온다.

int main(int argc, char *argv[])
{
int targetnumber = 0;
int nownum;

scanf("%d", &targetnumber);

for (nownum = 1; nownum < targetnumber; nownum++)
if (targetnumber % nownum == 0)
printf("%d는 %d의 약수. \n", nownum, targetnumber);

printf("Complete\n");

return 0;
}

위의 코드로 별다른 문제없이 모든 약수를 찾아낼 수 있다. 한 1000000000정도까지는 그렇다.(0이 9개다.)
2000000000(0이 9개)를 입력해보면.. 검색시간이 진정 초단위로 걸린다. 만약 사용하는 변수들이 int보다 큰 long등의 형태를 띄었다면, 이는 버그인가 싶을수준의 검색시간을 보여줄 것이다.

이 글에서는 위와 동일한 약수 검색결과를 훨씬 빠른시간내에 찾아내는 알고리즘을 설명하고자 한다.

설명에 앞서, 앞으로 설명할 알고리즘의 주요 토대가될 약수들간의 규칙을 먼저 소개하고자 한다.
예시를 들어 설명하자면, 6의 약수는 1, 2, 3, 6이다. 우리가 만약 위의 코드를 통해서 6의 약수를 검색하고자 한다면, for문에서 1, 2, 3, 4, 5, 6을 if문으로 직접 검사한 다음에 위의 결과를 낼 수 있을 것이다. 그러나 사실, 3~6은 검사할 필요가 없다. 검색할 숫자 6과 1, 2가 6의 약수라는걸 안 시점에서, 우리는 3과 6이 6의 약수라는걸 자연스럽게 알 수 있기 때문이다. 어떻게? 6으로 1과 2를 각각 나눠봐서.

잘 와닿지 않는다면 검색대상숫자를 크게 높여서 알아보자. 100의 약수는 다음과 같다.
1, 2, 4, 5, 10, 20, 25, 50, 100
만약 우리가 1, 2, 4, 5가 100의 약수임을 확인했다면, 마찬가지로 20, 25, 50, 100이 100의 약수임을 알 수 있다.
100 / 1 = 100, 100 / 2 = 50, 100 / 4 = 25, 100 / 5 = 20 이니까.
이렇게, 전체 약수의 반정도만을 파악한 시점에서 검색을 종료해도 문제없는 결과를 보여줄 수 있다.
다만 이러한 방법으로는 약수의 갯수가 홀수개일때, 약수들을 순서대로 나열했을경우 가운데에 위치하는 약수를 파악하는 것이 불가능하다. 다만 이 경우 sqrt(검색대상수)가 해당 약수이므로 어렵지 않게 찾을 수 있다.

위의 규칙에 기반하여 약수를 검색할 경우, 1부터 sqrt(검색대상수) - 1까지 검사하면 된다. 예시로들었던 100은 1부터 9까지만 검사하면 되는 것이다. 검색대상을 100개에서 9개로 줄였으니, 특별한 문제가 없다면 속도향상은 보장된 것이나 다름없다. 검색대상숫자가 클수록 더 높은 효율을 보여줄 것이다.(검색대상수가 10000이라면 99까지만, 100000000이라면 9999까지만..)

아래는 이러한 특징에 기반하여 짠 코드이다.

typedef struct rawstack{
int datanum;
struct rawstack *prev;
}Stack; //스택 자료구조 선언

Stack *divisor_early = NULL; //먼저나오는 약수들을 저장할 스택

void PushStack(int pushingData); //스택에 대한 push함수
Stack* CreateElement(int pushingData); //스택 할당 함수
int PopStack(); //스택에 대한 pop함수

int main(int argc, char *argv[])
{
int targetnumber; //약수검색대상 수를 저장할 변수
int nownum;

Stack *nowElement;

printf("약수를 검색할 대상이 되는 수를 입력하세요(> 1) : ");
scanf("%d", &targetnumber);

if (targetnumber <= 0){ //입력 예외처리
printf("이 프로그램에서는 검색 불가능한 수입니다. \n");
return 0;
}

printf("1은 %d의 약수입니다.\n", targetnumber);

for (nownum = 2; nownum * nownum < targetnumber; nownum++){
if (targetnumber % nownum) //약수여부 검사, true==1, false==0인 속성을 이용하여 나머지연산결과가 0인지 검사하는 연산(!= 0)을 생략하고자 하였음
continue; //약수가 아니면 아래의 과정을 통과

printf("%d는 %d의 약수입니다.\n", nownum, targetnumber);
PushStack(nownum); //도출된 약수를 스택에 저장
}

if (nownum * nownum == targetnumber) //가운데 약수 검사
printf("%d는 %d의 약수입니다.\n", nownum, targetnumber);

while (divisor_early != NULL) //위에서 얻은 약수로 추론가능한 약수들을 출력하는 과정
printf("%d는 %d의 약수입니다.\n", targetnumber / PopStack(), targetnumber);

if (targetnumber != 1) //대상수가 1일때 중복출력 방지
printf("%d는 %d의 약수입니다.\n", targetnumber, targetnumber);

printf("Complete\n");

return 0;
}

void PushStack(int pushingData){
if (divisor_early == NULL){ //스택의 첫번째 원소를 삽입시
divisor_early = CreateElement(pushingData);
return;
}

Stack *nowHead = divisor_early;
divisor_early = CreateElement(pushingData);
divisor_early->prev = nowHead;
}

Stack* CreateElement(int pushingData){ //스택 원소삽입 처리
Stack *newstack = (Stack*)malloc(sizeof(Stack));

newstack->datanum = pushingData;
newstack->prev = NULL;
return newstack;
}

int PopStack(){
Stack *prevElementFromHead = divisor_early->prev;
int poppingData = divisor_early->datanum;

free(divisor_early);
divisor_early = prevElementFromHead;

return poppingData;
}

main함수 외에는 위에서 말했던 sqrt(검색대상수)미만의 약수들을 저장하기 위한 스택과 관련된 코드이다. 고로 약수검색에만 관심이 있다면 main함수만 봐도 무방하다.

위에서는 설명하지 않았지만, 1을 제외한 모든 자연수는 반드시 1과 자신을 약수로 포함한다. 이점을 이용하여 위 코드는 두 수를 각각 검색하지 않도록 하였다.

main함수의 기존의 코드와 비교해볼때 위 코드 main함수의 for문 조건에 유념할 필요가 있다. 해당 조건(nownum * nownum < targetnumber)이 sqrt(검색대상수) - 1까지의 검색을 보장하는 부분이다. sqrt함수의 비효율성과 부동소수점연산 회피를 위하여 이러한 조건을 사용하였다.

for문 반복시마다 검사결과 어떤수가 약수라면 스택에 저장해둔다. for문의 검색이 종료되면 남은 할일은 간단하다.
일단 약수의 갯수가 홀수일 경우 발생하는 sqrt(검색대상수)약수를 처리한다.
사실 홀수개의 약수가 존재하게되는 원인, 약수들을 차례대로 나열했을경우 가운데에 위치하는 약수가 도출되는 이유는 약수검색 대상수가 어떤 숫자를 제곱한 결과와 같기때문이다. 따라서 이런경우 필연적으로 sqrt(검색대상수)약수를 가지게된다.

nownum * nownum == targetnumber조건으로 이 약수를 도출시킬 수 있다. nownum은 for문을 돌고나면 sqrt(검색대상수)를 올림시킨 정수값을 가지고있을 것이다. 검색대상수가 100(sqrt(100) = 10)일경우와 101(sqrt(101) = 10.04...)일 경우를 가정해보자.
100일경우 nownum은 10일 것이고(10 * 10 < 100일때 for조건이 거짓이되므로 탈출)
101일경우 nownum은 11일 것이다.(10 * 10 < 101은 참이므로 for문을 한번더 반복, 11 * 11 < 101은 거짓이므로 for문을 탈출)
100일경우 10 * 10 == 100이 참이므로 10을 약수로 도출한다.
101일경우 11 * 11 == 101이 거짓이므로 11을 약수로 도출하지 않는다.
이러한 원리로 sqrt(검색대상수)약수를 도출시키는 것이다.

이제 나머지 약수를 도출시킬 차례다. 스택에서 하나씩 꺼내어 나머지 약수를 찾으면 된다.
예시로들었던 100을 검색대상수로 설정했다면 아마 for문 완료후 스택에는 다음과 같이 저장되어있을 것이다.

2, 4, 5(head)

head부터 하나씩 pop하면서 검색대상수로 이를 나눠주면 검색되지않은 약수가 튀어나온다.
100 / 5 = 20
100 / 4 = 25
100 / 2 = 50.

아까 말한대로 모든 수는 1과 자기자신을 약수로가지므로 자기자신 100을 다이렉트로 도출하고나면 모든 약수가 도출된 것이다.


이 코드로 맨 위의 코드에서 시간이 한참걸렸던 2000000000을 입력하고 엔터를 치면 어지간한 컴퓨터로는 엔터키를 누르자마자 끝날것이다.

덧글|덧글 쓰기|신고