프로그래밍

3198,

1/160

lmi

http://super-user.co.kr

질문드립니다. ㅠㅠ

http://www.hackerschool.org/HS_Boards/zboard.php?AllArticle=true&no=2994 [복사]

#include <stdio.h>
int find_divisor(int);
int main (void){
        int a,b,c=0;
        scanf("%d %d",&a,&b);
        for(;a<=b;a++){
                if(find_divisor(a) == 1)
                        c += 1;
        }
        printf("%d",c);
}
int find_divisor(int a){
        int i,i2=0;
        for(i=1;i<=a;i++){
                if(a%i == 0)
                        i2 += 1;
        }
        if(i2%2 == 0)
                return 1;
        else
                return 0;
};

위는 제가 어떤 문제를 풀면서 작성한 프로그램인데요..

뭔가 과정에서 문제가 있는지좀 살펴주셨으면 합니다..

제가 imac으로 xcode통해서 컴파일을 했는데요

실행시켜보면 입력 값의 범위가 10000이상이 되면

계산하는데 1초이상 시간이 소요되면 값이 커질수록

계산 시간이 엄청나게 길어지네요 ㅠㅠ

문제는
두 정수 A, B (1 <= A <= B <= 2,000,000,000) 가 주어질때 A 와 B 사이 (A, B 포함) 에 약수 개수가 짝수인 수 개수를 출력하시오.
입력
두 정수 A, B 가 주어진다.
출력
약수 개수가 짝수인 수의 개수를 출력하시오.
입니다만...

Hit : 4483 Date : 2011/05/13 03:19


hayanho	아마 context switching 과 관련해서 확인해 보시면 될 것 같습니다. 말씀 드릴려는 내용은 함수를 너무 여러번 과다하게 호출하다보니 느려지는 것으로 보입니다.	2011/05/13
화련한	더블릿 문제인가요? 이건 알고리즘 문제네요. 만약에 A가 1이고 B가 2,000,000,000이라고 생각해봅시다. 그러면 연산횟수는 총 몇번이 될까요? 우선 main에 있는 for문이 총 2,000,000,000 돌게 됩니다. 그런데 그 for안에 잇는 find_divisor는 총 몇번 돌게 될까요? 그건 a의 크기에 달려있습니다. a가 1이면 1번, 2면 2번...해서 마지막에는 2,000,000,000번을 돌게 됩니다. 그러므로 총 1+2+....+2,000,000,000번을 돌게 됩니다. 정확한 값은 (n*(n+1))/2로 확인하면 되겠죠. 즉, 그런 방법으로 짰다간 답을 구하려면 평생가도 못구할수도 있습니다. 그러므로 다른 알고리즘을 생각해야 합니다.	2011/05/13
lmi	아하..	2011/05/16