자료형 내의 최대 소수 구하기

최대소수 구하기

소수란 자기자신과 1로만 나누어지는 수로, 2, 3, 5, 7, 11... 로 거의 규칙없이 존재한다.

 

판별 조건

소수인지 판별하는 방식으로는 자신보다 작은 모든 숫자로 나누어보고 나누어지는 숫자가 없으면 소수라고 판별할 수 있다.

 

최적화

하지만 모든 숫자를 나누면 비효율적이므로, 대칭성의 원리를 이용하자. 2부터 자신의 제곱근까지만 탐색한다.

 

def is_prime(num):
    for i in range(2, int(math.sqrt(num))+1):
        if num%i == 0:
            return False
    return True

 

 

C언어 자료형	최댓값	최대 소수
(signed) int (long)	2,147,483,647	2,147,483,647
unsigned int (long)	4,294,967,295	4,294,967,291
(signed) long long	9,223,372,036,854,775,807	9,223,372,036,854,775,783
unsigned long long	18,446,744,073,709,551,615	18,446,744,073,709,551,557

 

unsigned long long의 최대 소수를 구하는데도 495초 정도가 소요됐다.

 

 

파이썬...

파이썬 내에의 자연수를 나타내는 자료형은 int와 float이 있다.

int 자료형의 최댓값은 숫자가 커질수록 추가로 메모리를 할당받아 표기하므로 사실상 무한대에 가깝다고 볼 수 있다...ㄷㄷ

float자료형을 사용하면 float('Inf')로 표현하는 무한이 존재하는데, 이 값은 약 1.8 * e+308로, 이 숫자범위 내의 소수를 판별하기 위해서 매우 긴 연산시간이 소요되기 때문에 파이썬 상에서 표기할 수 있는 최대 소수를 구하려면 뭔가 다른방법을 찾아봐야할 것 같다..

+ math.sqrt로 저 숫자의 제곱근을 구하면 "OverflowError: int too large to convert to float"이라는 에러가 출력되는데, math라이브러리 상에서 계산할 수 있는 최대 정수가 따로 존재하는 듯 하다. 이를 이용하면 math라이브러리에서 계산 가능한 최대 소수를 구할 수 있을 지도 모르겠다.

 

 

 

++ 실험적으로 약간의 노가다를 해본결과 2^1024 - 2^ 970 - 1이 연산가능 한 최대 정수인 것으로 보인다. 이를 숫자로 표현하면

179769313486231580793728971405303415079934132710037826936173778980444968292764750946649017977587207096330286416692887910946555547851940402630657488671505820681908902000708383676273854845817711531764475730270069855571366959622842914819860834936475292719074168444365510704342711559699508093042880177904174497791

이고, 이 범위 내의 가장 큰 소수는 소수를 찾아주는 웹페이지에서 검색한 결과,

179769313486231580793728971405303415079934132710037826936173778980444968292764750946649017977587207096330286416692887910946555547851940402630657488671505820681908902000708383676273854845817711531764475730270069855571366959622842914819860834936475292719074168444365510704342711559699508093042880177904174497101

 

로 계산되었고, 컴퓨팅 성능 상 파이썬에서 확인은 불가능하였다..