Maintenance script: Table transclusion repair v1

2026-03-27T12:46:16Z

Table transclusion repair v1

← Older revision		Revision as of 12:46, 27 March 2026
Line 1:		Line 1:
	==== 소감 ====		==== 소감 ====
	~~{{\|~~ 2005/05/09 Accepted 0:02.826 452 ~~\|}}~~		2005/05/09 Accepted 0:02.826 452

	중간에 발생하는 버그를 잡는데 대부분의 시간을 허비했다. 65000 이란 수는 작지만 65000의 제곱은 int형의 범위를 벗어난다. ㅡㅡ; 오버플로우를 교모히 이용한 함정에 고생했다.		중간에 발생하는 버그를 잡는데 대부분의 시간을 허비했다. 65000 이란 수는 작지만 65000의 제곱은 int형의 범위를 벗어난다. ㅡㅡ; 오버플로우를 교모히 이용한 함정에 고생했다.
Line 107:		Line 107:
	----		----
	[[CarmichaelNumbers]] [[AOI]]		[[CarmichaelNumbers]] [[AOI]]

imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:48Z

New page

==== 소감 ====
{{| 2005/05/09 Accepted 0:02.826 452 |}}

중간에 발생하는 버그를 잡는데 대부분의 시간을 허비했다. 65000 이란 수는 작지만 65000의 제곱은 int형의 범위를 벗어난다. ㅡㅡ; 오버플로우를 교모히 이용한 함정에 고생했다.
Carmichael Numbers를 찾는 Theorem이 있는 듯하다. 그러나 때려맞추기(?)로 문제를 풀어도 풀린다. 그러나 속도는 떨어진다.

==== 코드 ====
// 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;
}
----
[[CarmichaelNumbers]] [[AOI]]

CarmichaelNumbers/문보창 - Revision history

Maintenance script: Table transclusion repair v1

imported>Unknown at 05:22, 7 February 2021