[C] 소수 인지 확인하기

[C] 소수 인지 확인하기

소수의 정의

1과 자기자신 외에는 나누어 떨어지는 정수가 없는 양의 정수

입력받은 N을 2부터 N-1까지의 정수로 나누어서 나누어 떨어지는 수가 있으면 소수가 아니고, 나누어 떨어지는 수가 없으면 N은 소수가 된다.

1. 정수 N을 입력받는다.

2. 정수 i에 2를 대입한다.

2.1 N이 i로 나누어 떨어지는가?

2.1.1 나누어 떨어지면 소수가 아니다 끝.

2.2 i를 하나 증가시킨다.

2.3 i가 N보다 작은가?

2.3.1 작으면 2.1로 돌아간다.

3. 정수 N은 소수이다. 끝.

#define TRUE 1

int is_prime(int n){

    int i;
    for (i = 2; i < n; i++){
        if (n%i == 0)
            return !TRUE;        
    }
    return TRUE;
}

위의 알고리즘에서 개선의 여지가 있다.

2부터 N-1 까지의 숫자의 나머지를 구하는 계산을 하면 중복되는 계산이 나온다.

13을 예로 들면,  (2*6)+1 과 (6*2)+1 은 같으므로, 2와 6의 연산은 중복이 되게 된다.

따라서 반복 계산은 2부터 N의 제곱근까지만 확인해도 된다.

#include <math.h>

#define TRUE 1

int is_prime2(int n){

    int i, sqrn;
    sqrn = (int)sqrt(n);
    for (i = 2; i <= sqrn; i++){
        if (n%i == 0)
            return !TRUE;
    }
    return TRUE;
}

sqrt() 함수는 제곱근을 구하는 함수로 math.h 를 include 해야한다.

반복 연산의 횟수는 반절로 줄었지만, 주의해야 할 부분이 있다.

sqrt() 함수는 실수를 계산하는 함수로, 정수보다 많은 연산을 소요한다.

따라서, 상황에 따라 정수만은 연산하는 첫번째 알고리즘보다 느린 속도를 가져오는 경우도 있다.

입력된 숫자 N이 작은 수일 경우는 첫번째 알고리즘이 빠른 속도를 내지만, 숫자 N이 클 경우 두번째 알고리즘이 빠른 속도를 낸다.

main 함수

#include <stdio.h>

void main(void){
    
    int n;

    puts("\n PRIME1 : Test that input number is prime or not."
        "\n           Input 0 to end program ");

    while (TRUE){
        puts("\nInput number to test -> ");
        scanf_s("%d", &n);

        if (n < 0)
            continue;
        if (n == 0)
            break;
        printf("\n Ans using is_prime()  : %d is %s prime number", n, is_prime(n) ? "" : "not");
        printf("\n Ans using is_prime2() : %d is %s prime number", n, is_prime2(n) ? "" : "not");
    }
}

출처: https://hyeonstorage.tistory.com/337?category=622873 [개발이 하고 싶어요]