백준 4233번: 가짜소수

https://www.acmicpc.net/problem/4233

4233번: 가짜소수

---

본문에서 페르마의 소정리를 친절하게 설명해주고 있습니다.

 

그러나 예제 출력을 잘 보면 알 수 있듯이, 어떤 수 p가 밑 a에 대해 페르마의 소정리를 만족하더라도 가짜소수가 아닐 수 있습니다.

 

따라서, 

 

p가 밑 a에 대해 페르마의 소정리를 만족하는지 확인한 후,

 

만약 만족한다면 p가 "소수"인지 아닌지를 판별하면 됩니다.

 

본문에 나와있듯이 p가 최대 $10^{9}$ 이므로, $O\left ( \sqrt{N} \right )$ 방식으로 p가 소수인지 아닌지 따져주면 충분합니다.

 

#include <stdio.h>
#include <stdbool.h>

bool IsPrime (int a);

long long add_modular (long long x, long long y, long long M);
long long multiply_modular (long long x, long long y, long long M);
long long power_modular (long long x, long long y, long long M);

int main() {
	long long p, a;
	scanf("%lld %lld", &p, &a);
	while (a != 0 && p != 0) {
		if (a == power_modular(a, p, p)) {
			if (IsPrime(p)) {
				printf("no\n");
			}
			else {
				printf("yes\n");
			}
		}
		else {
			printf("no\n");
		}
		scanf("%lld %lld", &p, &a);
	}
	return 0;
}

bool IsPrime (int a) {
	if (a == 1) {
		return false;
	}
	else if (a == 2 || a == 3 || a == 5 || a == 7) {
		return true;
	}
	else if (a % 2 == 0) {
		return false;
	}
	else {
		int i;
		for (i = 3; i * i <= a; i += 2) {
			if (a % i == 0) {
				return false;
			}
		}
		return true;
	}
}

long long add_modular (long long x, long long y, long long M) {
	x %= M;
	y %= M;
	if (x >= M - y || y >= M - x) {
		return (x - M) + y;
	}
	else {
		return x + y;
	}
}

long long multiply_modular (long long x, long long y, long long M) {
	x %= M;
	y %= M;
	long long result = 0;
	while (y > 0) {
		if (y & 1) {
			result = add_modular (result, x, M);
		}
		x = add_modular (x, x, M);
		y >>= 1;
	}
	return result;
}

long long power_modular (long long x, long long y, long long M) {
	x %= M;
	long long result = 1;
	while (y > 0) {
		if (y & 1) {
			result = multiply_modular (result, x, M);
		}
		x = multiply_modular (x, x, M);
		y >>= 1;
	}
	return result;
}

 

C11, 1116KB, 0ms입니다. (제출 번호 25525653)

---

이번 글에 올린 코드는 실제 제출했던 코드와 약간의 변경점이 있습니다.

1) 42번째 라인의 i += 2가 원래 i++이었습니다. 이를 i += 2로 바꾸면서, 연산 횟수가 절반으로 줄었다고 볼 수 있습니다.

2) 진짜 사소하지만 11번째 라인에서 p, a 가 원래 a, p로 되어있었는데, 코드를 짤 때 변수 선언한 순서대로 scanf("%lld %lld", &a, &p);라고 쓰는 해프닝이 있었어서 수정했습니다.

 

또, 이번 문제는 $10^{9}$ 안의 숫자만 고려하기 때문에, power_modular 함수만 구현했더라도 충분했을 것 같습니다.

 

마지막으로, 페르마의 소정리는 밀러-라빈 소수 판정법과도 연관이 있어서, 이 문제를 통해 미리 연습해보면 좋을 것 같습니다.

---

 

(2022-01-20 수정)

 

#include <stdio.h>
#include <stdbool.h>

bool IsPrime (int a);

long long power_modular (long long x, long long y, long long M);

int main() {
	while (1) {
        
        long long p, a;
        scanf("%lld %lld", &p, &a);
        if (p == 0 && a == 0)
        {
            break;
        }
		
        if (a == power_modular(a, p, p)) {
			if (IsPrime(p)) {
				printf("no\n");
			}
			else {
				printf("yes\n");
			}
		}
		else {
			printf("no\n");
		}
	}
	return 0;
}

bool IsPrime (int a) {
	if (a == 1) {
		return false;
	}
	else if (a == 2 || a == 3 || a == 5 || a == 7) {
		return true;
	}
	else if (a % 2 == 0) {
		return false;
	}
	else {
		for (int i = 3; i * i <= a; i += 2) {
			if (a % i == 0) {
				return false;
			}
		}
		return true;
	}
}

long long power_modular (long long x, long long y, long long M) {
	long long result = 1;
	while (y) {
		if (y & 1) {
			result = result * x % M;
		}
		x = x * x % M;
		y >>= 1;
	}
	return result;
}

(C11, 1116KB, 0ms, 제출번호 37850626)