소수 판별(1) (C언어)

소수는 1과 자기자신을 제외하고 나누어 떨어지는 수가 없는 수입니다.

 

먼저 단순히 2부터 시작해서 하나씩 나누어 떨어지는지 판별하는 코드 입니다.

#include<stdio.h>
int isprimeNumber(int x) { //소수 판별 (시간복잡도가 많이 듬)
	for (int i = 2; i < x; i++) {
		if (x % i == 0)
			return 0; //합성수
	}
	return 1; //소수
}
int main(){
    int n;
    scanf("%d",&n);
    if(isprimeNumber(n)==1)
       printf("소수");
    else
       printf("합성수);
       
    return 0;
 }

 보시는 바와 같이 for문에서 i가 2부터 x-1 까지 순서대로 x와 나누어 떨어지는지 확인합니다.

물론 n이 작은 수면 상관 없지만 큰 수가 들어오면 하나하나 나누어 떨어지는지 확인할때 시간을 많이 소비할 수 밖에 없습니다.

따라서 조금 다르게 생각해봅니다.

---

결론 부터 말하면 n의 제곱근까지만 나누어 떨어지는 지 확인해서

만약에 2부터 시작해서 n의 제곱근까지 나누어 떨어지는 수가 있으면 합성수 이고 그렇지 않으면 소수입니다.

예를들어 n이 100이면  √100= 10 이므로 2부터 10까지 100으로 나누어 떨어지는 수가 있는지 확인하면 되는 겁니다.

√100 * √100 =100이므로 √100 이상인 약수는 결국 √100 이하의 수와 약수 짝을 이루게 되기 때문에 우리는

약수 짝 중에 작은 수만 판별하면 되는 것입니다.

100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100 입니다. 결국 2, 4, 5, 10 이 100과 나누어 떨어지는 지 확인하면 됩니다.

#include<stdio.h>
int isprimeNumber2(int x) { //소수 판별(x의 제곱근까지 소수 판별하면 됨)
	for (int i = 2; i*i<=x; i++) {
		if (x % i == 0)
			return 0;//합성수
	}
	return 1;//소수
}
int main(){
    int n;
	scanf("%d", &n);
	if (isprimeNumber2(n))
		printf("소수");
	else printf("합성수");
    
    return 0;
}

for문을 자세히 보면 i가 2부터 시작해서 i * i <= x 일때 까지 돌아가는것을 보실 수 있습니다. 

결국 x가 100이면 i는 10까지 돌아갈 수 있다는 뜻 입니다.

첫번째 소수 판별식은 for문에서 i가 2부터 99까지 돌아갔다면 이번에는 i가 2부터 10까지 밖에 안돌아가 

상대적으로 시간복잡도가 줄어들었습니다.