정올 알고리즘 사이트에서 풀었던 문제를 기억하기위해 적어둠

문제 번호: 1011

문제 URL: http://jungol.co.kr/problem.php?ctc=04&id=1011

내가 푼 코드

<code C>
#include <stdio.h>

int is_prime(int param_v);
int compute(int param_n, int param_m, int param_k);
double copied_sqrt(int number);

int main(int argc, char* argv[]) {

    int N = 0;
    int M = 0;
    int K = 0;
    
    int count = 0;

    scanf("%d %d %d", &N, &M, &K);

    count = compute(N, M, K);
    printf("%d\n", count);

    //printf("argc=%d, argv=%s\n", argc, argv[0]);
    return 0;
}

int compute(int param_n, int param_m, int param_k) {

    int i = 0;
    int count = 0;
    if (param_n < 2) {
        return -1;
    }

    for (i = (param_k + 1); i <= param_m; i = i + param_n) {
        if (is_prime(i) == 1) {
            count = count + 1;
        }
    }

    return count;
}

int is_prime(int param_v) {

    int i = 0;
    int sqrt_value = 0;
    int is_not_prime = 0;

    if (param_v == 1) {
        return 1;
    }

    sqrt_value = (int)copied_sqrt(param_v);
    for (i = 2; i <= sqrt_value; i++) {
       if (param_v % i == 0) {
           is_not_prime = 1;
           break;
       }
    }

    return (is_not_prime == 1) ? 0: 1;
}

double copied_sqrt(int number) {

    double t;
    double squareRoot = number / 2;
    do {
        t = squareRoot;
        squareRoot = (t + (number / t)) / 2;
    } while ((t - squareRoot) != 0);

    return squareRoot;
}

</code>

특정한 수가 소수인지 확인 하는 가장 쉬운 방법은
그 수가 가지는 범위의 수들로 하나씩 나눠 보는 것이다.

이 경우, 수의 범위가 큰 경우에는 확인에 필요한 시간이 그만큼 길어진다.

위키 피디아에 정리된 [[https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_%28%EC%88%98%EB%A1%A0%29#.EC.86.8C.EC.88.98_.EC.B0.BE.EA.B8.B0|소수 찾기 부분]]을 참고하면 계산해야 하는 범위를 루트 n(제곱근)까지로 좁힐 수 있기 때문에
필요한 시간을 줄일 수 있다.

알고리즘 통과에 필요한 제한 시간 1초내에 계산이 가능하다.

제곱근 계산에 대한 부분은 [[http://www.programcreek.com/2012/02/java-calculate-square-root-without-using-library-method/|Java Calculate Square Root Without Using Library Method ]]의 소스를 그대로 사용하였다.

문제를 풀고나서 문제 출제 의도를 생각해 보니
출제자는 시험자가 제곱근 계산 코드를 구현할 수 있는지를 테스트 해보려는 의도였던 것 같다.