[Algorithm] 소수를 판별하는 알고리즘

 1보다 큰 임의의 정수를 입력하여 소수를 판별 

1. 입력받은 숫자보다 작은 모든숫자를 다 나누어본다.

어떤 수 X가 소수 인지를 판별하려면 X를 2부터 X보다 작은 수(X-1)까지 차례대로 나누어 떨어지는지 검사하면 됩니다. 예컨데 5는 2,3,4,로 나누었을때 한번도 나누어 떨어지지 않으므로 소수이고, 4는 2로 나누었을때 나누어 떨어지므로 소수가 아닙니다.

C언어 / C++ 코드

#include<stdio.h>
main(){
    int a, i, j;
    scanf("%d",&a); //정수형 변수 a에 정수를 입력받습니다.
    i=2;
    j=a-1;

    f(a==1){ //1은 소수가 아님
        printf("소수아님");
        return; 
    }
	
    while(1){ //무한루프 
        if(i<=j){ 
            if(a%i==0){ //i가 나누어떨어지면 소수가 아님 
                printf("소수아님");
                break; 
            }else{
                i++;
            }
       }else{ //i가 j보다 커질때까지 나누어떨어지지 않으면 소수 
            printf("소수");
            break;
        }
    } 
}

 

 

방법 2 : 입력받은 숫자의 제곱근 까지의 숫자로 나누어본다.

사실 입력받은 숫자부터 작은 수 까지 전부 다 나눠볼 필요는 없습니다. 정확히는 입력받은 X를 2부터 X의까지 제곱근까지의 숫자만 나누어 떨어지는지 확인하면 됩니다. 예를 들어 25는 2, 3 ,4 ,5,로 나누었을 때 5로 나누어 떨어지므로 소수가 아니고 41은 2,3,4,5,6,으로 나누어도 한번도 나누어 떨어지지 않으므로 소수입니다.

C언어 / C++ 코드

#include<stdio.h>
#include<math.h> //sqrt()함수가 있는 헤더파일입니다. 

main(){
    int a, i, j;
    scanf("%d",&a); //정수형 변수 a에 정수를 입력받습니다.
    i=2;

    if(a==1){ //1은 소수가 아님
        printf("소수아님");
        return; 
    }
	
    while(1){ //무한루프 
        if(i<=sqrt(a)){ 
            if(a%i==0){ //i가 나누어떨어지면 소수가 아님 
                printf("소수아님");
                break; 
            }else{
                i++;
            }
        }else{ //i가 j보다 커질때까지 나누어떨어지지 않으면 소수 
            printf("소수");
            break;
        }
    } 
}