C언어, 다음 소수 찾기

특정 수가 주어진다면 특정 수이상인 소수중 가장 작은 소수를 찾는 알고리즘을 만들어 보도록 하겠습니다.

 

우선 소수임을 판별해 주는 함수가 필요합니다.

저희는 OdOp_next함수에서 판별하겠습니다. 

 

OdOp_next

int    OdOp_next(long long nb)
{
    long long    i;
    long long    standard;

    i = 2;
    standard = OdOp_sqrt(nb);
    while (nb % i != 0 && i <= standard)
    {
        i++;
    }
    if (i <= standard)
    {
        return (0);
    }
    return (1);
}

위의 함수가 아직은 잘 이해되지 않으시는 분들은 아래의 링크를 참고해 주시길 바랍니다. 

(https://hig0617.tistory.com/109)

 

여기서 전의 포스팅과 다른 점이 한가지 있습니다. 바로 standard죠.

이제 standard를 구하는 함수를 만들어 보도록 하겠습니다. 

저희는 OdOp_sqrt함수에서 standard를 만들겠습니다. 

 

OdOp_sqrt

int    OdOp_sqrt(long long n)
{
    long long    standard;

    standard = 1;
    while (standard * standard < n)
    {
        standard++;
    }
    return (standard);
}

standard는 제곱근을 찾는 것입니다. 

 

standard는 1부터 차근차근 1씩 증가합니다. 그러다가 n보다 같거나 커졌을 때의 standar를 리턴해줍니다. 

예를 들어 n이 36이라고 하겠습니다. 그러면 standard는 1부터 차근차근 1씩 증가하면서 6이 되었을 때에 while문을 종료하고 standard 즉, 6을 리턴해 줍니다. 

하나만 더 해보죠. 이번에는 n이 47입니다. 그러면 standard는 마찬가지로 6까지 증가했을 때 6의 제곱은 36이기 때문에 47보다 작습니다.

그렇기 때문에 standard를 다시 증가시켜 7을 만듭니다. 이때 제곱은 49가 됩니다. 49는 n(47)보다 큽니다. 따라서 while문이 종료가 되고 standard는 7이 됩니다. 

 

왜 제곱근으로 진행을 했을까요???

36의 약수를 생각해봅시다. 

1, 2, 3, 4, 6, 9, 12, 18, 36이 됩니다. 

2 * 18 = 36

3 * 12 = 36

4 * 9 = 36

6 * 6 = 36

혹시 눈치 채셨나요???

2로 나누는 것과 18로 나누는 것의 결과를 똑같다고 보아도 무방하게 됩니다. 즉 제곱근 아래로만 진행하면 되겠죠.

 

이제 위의 함수들만 잘 합치면 다음 소수를 찾을 수 있습니다. 

저희는 OdOp_find_next_prime에서 합치겠습니다. 

 

OdOp_find_next_prime

int    OdOp_find_next_prime(int nb)
{
    if (nb <= 2)
        return (2);
    while (!(OdOp_next((long long)nb)))
        nb++;
    return (nb);
}

만약 nb가 소수이면 OdOp_next(nb)는 1이 됩니다. 

이렇게 되면 바로 nb를 리턴해줍니다. 

그렇지 않고 OdOp_next(nb)가 0이 되면, nb를 하나씩 증가하면서 소수를 찾게 됩니다. 

 

궁금증이 잘 해결되셨으면 좋겠습니다.