알고리즘(1) - 소수, 약수, 소인수분해 등

목차

1-1. 소수의 합 구하기

1-2. 소수의 개수 구하기

1-3. 두 수의 최대공약수와 최소공배수 구하기

1-4. 약수 구하기

1-5. 소인수분해

1-1. 소수의 합 구하기

 > 임의의 정수를 입력받아 그 안에 포함된 소수의 합을 구하는 코드.

내 코드

int main()
{
    int a, sum, j, k;
 
    sum = 0; k = 2;
 
    printf("입력값 : ");
    scanf("%d", &a);
    printf("\n");
 
    do {
        for (j = 2; (k%j) > 0; j++) {
 
        }
        if (j == k) {
            sum += k;
        }
        k++;
        printf("a=%d j=%d k=%d sum=%d \n",a,j,k,sum);
    } while (k < a);
 
    printf("\n");
}

*틀렸던 부분 : 

교재 코드

int main()
{
    int a, hap, k, j;
 
    scanf("%d", &a);
    hap = 0;
    k = 2;
 
    while (1){
        j = 2;
        while (k%j != 0) {
            j++;
            if (k == j)
                hap += k;
 
            if (k < a)
                k++;
            else {
                printf("&d", hap);
                break;
            }
        }
    }    
}

입력값 : 10

출력값 : 17(2+3+5+7)

1-2. 소수의 개수 구하기

 > 배열 A[99]에 2~100 사이의 정수를 기억시킨 후 이 배열을 이용하여 소수의 개수를 구하시오.

내 코드

int main()
{
    int k, i, j, m;
 
    int a[99];
 
    for (i = 0; i < 99; i++) {
        a[i] = i + 2;
    }
    j = 0;
    for (i = 0; i < 99; i++) {
        if (a[i] != 0) {
            j++;
            k = a[i];
            for (m = i; m < 99; m += k) {
                a[m] = 0;
            }
        }
        else {
            
        }        
    }
 
    printf("k=%d i=%d j=%d m=%d \n", k, i, j, m);
    
}

*틀렸던 부분 : 

교재 코드

int main()
{
    int k, i, j, m;
    int a[99];
 
    k = 1;
    
    do {
        k++;
        a[k - 2] = k;        
    } while (k < 100);
 
    i = -1, j = 0;
 
    while (1) {
        i++;
        if (i > 98) {
            printf("%d", j);
            break;
        }
        if (a[i] == 0) {
            continue;
        }
 
        j++;
        m = i;
 
        while (1) {
            m += a[i];
            if (m > 98) {
                break;
            }
            a[m] = 0;
        }
    }
}

출력값 : 25(2와 100 사이의 정수 중 소수의 개수)

1-3. 두 수의 최대공약수와 최소공배수 구하기

 > 임의의 정수 2개를 입력받아 두 수의 최대공약수와 최소공배수를 산출.

내 코드

int main()
{
    int a, b, big, small, qtt, rmd, gcm, lcm;
    printf("정수 2개 입력 : ");
    scanf("%d %d", &a, &b);
 
    if (a > b) {
        big = a;
        small = b;
    }
    else {
        big = b;
        small = a;
    }
 
    do {
        qtt = big / small;
        rmd = big - (small*qtt);
        if (rmd == 0) {
            gcm = small;
            lcm = a * b / gcm;
            break;
        }
        else {
            big = small;
            small = rmd;
        }
    } while (1);
 
    printf("gcm = %d lcm = %d", gcm, lcm);
    
}

*틀렸던 부분 : 

교재 코드

int main()
{
    int a, b, big, small, mok, nmg, gcm, lcm;
    scanf("%d %d", &a, &b);
 
    if (a >= b) {
        big = a;
        small = b;
    }
    else {
        big = b;
        small = a;
    }
 
    while (1) {
        mok = big / small;
        nmg = big - mok * small;
 
        if (nmg == 0) {
            gcm = small;
            lcm = a * b / gcm;
            printf("%d %d", gcm, lcm);
            break;
        }
        big = small;
        small = nmg;
    }    
}

입력값 : 4 5

출력값 : 1 20

1-4. 약수 구하기

 > 정수를 입력 받아 약수를 구해 출력하는 코드를 작성하시오.

내 코드

int main()
{
    int a[100], b, c, d, qtt, rmd, i;
    printf("약수를 구할 정수를 입력 : ");
    scanf("%d", &b); //정수입력받음
    d = -1; //배열 인덱스
 
    printf("\n"); //줄바꿈
 
    for (c = 1; c <= b; c++) {
        qtt = b / c;  //몫 계산
        rmd = b - (qtt*c); //나머지 계산
        if (rmd == 0) {//나머지가 0이면 약수이므로 저★장
            a[++d] = c; //초기값이 -1이므로 쓸 때 마다 1씩 증가. 첫 번째는 0
        }
    }
    printf("입력값 : %d \n약수 : ", b); //입력한 정수 출력
    for (i = 0; i <= d; i++) {
        printf("%d ", a[i]);
    }
}

*틀렸던 부분 : 

 > 10번 줄 c값을 0으로 초기화해서 "Integer division by zero" 오류 발생

교재 코드

int main()
{
    int b, mok, nmg, i;
    int a[100];
 
    scanf("%d", &b);
    int c = 0, d = -1;
 
    while (1) {
        c++;
        if (c <= b) {
            mok = b / c;
            nmg = b - mok * c;
            if (nmg == 0) {
                d++;
                a[d] = c;
            }
        }
        else {
            printf("%d", b);
            for (i = 0; i <= d; i++)
                printf("%d ", a[i]);
            break;
        }
    }
}

1-5. 소인수분해

 > 정수를 입력 받아 소인수를 구해 출력하는 코드를 작성하시오.

내 코드

int main()
{
    int a[100], b, c, d, e, qtt, rmd=1;
    printf("정수 입력 : ");
    scanf("%d", &b);
    printf("\n");
    c = 0; //배열 인덱스
    d = 2; //제수
    while (b != d) {
        e = (int)sqrt(b);
        for (d = 2; rmd != 0; d++) { //인수 검색 반복
            if (d > e) {  //제수가 입력된 값의 제곱근보다 크면 제수에 입력값을 넣고 반복 종료
                d = b;
                break; 
            }
            qtt = b / d; //몫 계산
            rmd = b - (qtt*d); //나머지 계산
        }
        a[c] = d; //배열에 나머지가 0인 인수 저장
        c++;
        b = qtt; //다음 인수 탐색을 위한 변수 설정
    }
 
    for (int i = 0; i < c; i++) {
        printf("%d ",a[i]);
    }
}

*틀렸던 부분 : 

 > 반복문 로직 오류

교재 코드

int main()
{
    int b, c, d, e, mok, nmg;
    int a[100];
 
    scanf("%d", &b);
    c = -1;
 
    while (1) {
        d = 2;
        e = (int)sqrt(b);
        
        while (1) {
            if (d > e) {
                d = b;
                break;
            }
            mok = b / d;
            nmg = b - mok * d;
            if (nmg == 0)
                break;
            else
                d++;
        }
        c++;
        a[c] = d;
        if (b == d)
            break;
        b = mok;
    }
    for (int i = 0; i <= c; i++) {
        printf("%d ", a[i]);
    }
}

맨 위로