소수의 정의와 for 반복문을 이용하여, 주어진 수가 소수인지 아닌지 판별하는 문제입니다.
첫번째 방법은 소수의 정의를 그대로 이용하는 방법입니다. 약수가 1과 자기 자신밖에 없는 수를 소수라고 합니다. 따라서 약수의 수를 저장하는 변수를 만들고, 약수의 수가 2이면 소수, 그보다 많으면 소수가 아니라고 판단합니다.
#include <stdio.h>
int T, N;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &N);
int yaksu = 0;
for (int i = 1; i <= N; i++) {
if (N % i == 0) {
yaksu++;
}
}
if (yaksu == 2) {
printf("Prime\n");
} else {
printf("Not Prime\n");
}
}
return 0;
}
위 코드의 경우 주어진 수가 소수인지 판별하기 위해 1부터 N까지 모두 확인해야 하기 때문에 시간복잡도는 O(N)이 됩니다.
두번째 방법은 플래그를 이용하는 방법입니다. 플래그란 간단히 말해서 상태를 표시하는 것을 말합니다. 우리는 isPrime이라는 변수를 만들어서 주어진 수가 소수인지 아닌지를 표현할 것 입니다. i변수를 2 에서 부터 N - 1 까지 순회하면서 N 이 i로 나누어 떨어지면 i의 배수라는 의미이고, 이는 곧 N이 소수가 아님을 의미합니다. 따라서 isPrime 변수를 false로 바꾸어 주고 반복문을 탈출합니다.
#include <stdio.h>
int T, N;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &N);
bool isPrime = true; // 주어진 수가 소수라고 가정하고 시작합니다
for (int i = 2; i < N; i++) { // 2 부터 N - 1 까지 순회합니다
if (N % i == 0) { // 만약 N 이 i 로 나누어 떨어지면,
isPrime = false; // 소수가 아니라고 저장하고 반복문을 탈출합니다
break;
}
}
if (isPrime) printf("Prime\n");
else printf("Not Prime\n");
}
return 0;
}
위 코드 또한 2부터 N - 1까지 수를 모두 확인하므로 시간복잡도는 O(N)이나, 중간에 소수가 아님을 확인하고 바로 반복문을 빠져 나오므로 실제 시간은 훨씬 적게 소요될 것임을 알 수 있습니다.