LinDol's 실험실

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

문제 번호: 1011

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

내가 푼 코드

#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;
}

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

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

위키 피디아에 정리된 소수 찾기 부분을 참고하면 계산해야 하는 범위를 루트 n(제곱근)까지로 좁힐 수 있기 때문에 필요한 시간을 줄일 수 있다.

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

제곱근 계산에 대한 부분은 Java Calculate Square Root Without Using Library Method 의 소스를 그대로 사용하였다.

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