확대 l 축소

메르센 소수 판별, 지수와 순환마디길이로, 챗 GPT 훨씬 효율적인 방법

이빨 빠진 접시를 버리지 않고 반찬을 놓아먹는다. 한 많은 이세상을 살다보면 하자 없는 게 어디있다고. 중년까지 살아왔다면, 흠이 나고 금이 가기 마련이다. 그래서 이빨 빠진 접시를 버리지 않고 나는 보듬으련다. 난 지금 막막하다. 내일이 될지 모레가 될 지 모를 산산조각날 것같은 파탄이 눈앞에 어른 거린다. 그래도 쓰련다. 처참하게 쓰다가 쓰러지련다. 


메르센 소수 판별은 지수와 순환마디길이와의 관계를 이해한다면, 손쉽게 할 수 있다고 본다. 먼저 메르센 소수가 소수이려면, 지수가 소수이어야 하는 것은 모두가 잘 아는 사실이다. 그런데 메르센 소수가 합성수라면, 지수보다 1큰수 지수 배수보다 1큰수를 소인수로 갖는다는 사실을 알면 된다. 


여기에 지수보다 1큰 수나 배수보다 1큰 수가 2와 3의 배수가 아니라는 것을 알면 소신수분해 횟수를 확 줄일 수 있다. 특히 지수나 지수배수가 순환마디길이와 같다는 우너리까지 이해한다면, 순환마디길이보다 1큰 수 순환마디길이 배수보다 1큰 수가 메르센 소수가 합성수라면 소인수가 된다는 것 같지 알면 된다. 


예를 들어 2의 5제곱-1인 31은 지수 5보다 1큰 수 6, 2나 3의 배수이니까, 제외하고 다음 배수 10보다 큰수 11로 나눠본다. 나누어 떨어지니 않는다. 계속해서 15보다 1큰 수는 2의 배수이므로 제외하고 20보다 1큰 수는 3의 배수니까 제외하고 25보다 1큰 수는 2의 배수니까 제외하면, 30보다 1큰 수가 자기 자신이니 소수라고 판정할 수 있다. 


즉 11로만 나눠보면 소수 판별이 가능하다. 순환마디길이도 지수 5의 배수에 해당하는 15이므로, 15보다 1큰 수는 16으로 2의 배수니까 제외하면, 바로 소수라는 것을 판벙할 수 있다. 


2의 11제곱 -1인 2047은 지수 배수보다 1큰 수인 23과 89가 소인수이다. 결국 나누어떨어지니 합성수라는 것을 알 수 있다. 


이에 대해 챗GPT는 '이 방법론은 기존의 단순한 나눗셈 방식보다 훨씬 효율적이며, p의 소수성, 순환마디길이와의 관계를 잘 활용합니다."라고 평했다.

이전화면맨위로

확대 l 축소