소감 ¶
{{| 2005/05/09 Accepted 0:02.826 452 |}}
중간에 발생하는 버그를 잡는데 대부분의 시간을 허비했다. 65000 이란 수는 작지만 65000의 제곱은 int형의 범위를 벗어난다. ㅡㅡ; 오버플로우를 교모히 이용한 함정에 고생했다.
Carmichael Numbers를 찾는 Theorem이 있는 듯하다. 그러나 때려맞추기(?)로 문제를 풀어도 풀린다. 그러나 속도는 떨어진다.
Carmichael Numbers를 찾는 Theorem이 있는 듯하다. 그러나 때려맞추기(?)로 문제를 풀어도 풀린다. 그러나 속도는 떨어진다.
코드 ¶
~cpp // no10006 - Carmichael Numbers #include <iostream> #include <cmath> using namespace std; const int NORMAL = 1; const int CARMICHAEL = 2; bool isPrime(int n); void show(int n, int type); bool isCarmichael(int n); bool passFermatTest(int a, int n); int findModulo(unsigned int a, unsigned int n); int main() { int n; // n = input integer ( 2 < n < 65,000) while (cin >> n && n != 0) { if (isPrime(n)) { show(n, NORMAL); continue; } if (isCarmichael(n)) show(n, CARMICHAEL); else show(n, NORMAL); } return 0; } bool isPrime(int n) { for (int i = 3; i <= sqrt(n) + 1; i += 2) if (n % i == 0) return false; return true; } void show(int n, int type) { if (type == NORMAL) cout << n << " is normal.\n"; else cout << "The number " << n << " is a Carmichael number.\n"; } bool isCarmichael(int n) { for (int i = 2; i <= n - 1; i++) { if (!passFermatTest(i, n)) return false; } return true; } bool passFermatTest(int a, int n) { int modulo = findModulo(a, n); if (modulo == a) return true; return false; } int findModulo(unsigned int a, unsigned int n) { unsigned int modN = n; unsigned int expo = 2; unsigned int mod = (a * a) % n; unsigned int modulo = 1; while (1) { while (expo * 2 <= modN) { expo *= 2; mod = (mod * mod) % n; } if (modN - expo <= 6) { for (int i=0; i < modN-expo; i++) { mod = (mod * a) % n; } break; } else { modulo = (modulo * mod) % n; modN -= expo; expo = 2; mod = (a * a) % n; } } return (modulo * mod) % n; }