무제한 (또는 매우 높은) 길이의 정수 저장

Question

을 사이드 프로젝트로 사용합니다. 집에서 구운 프라임 생성 문제를 해결하기 위해 C 및 C++를 가르치는 수단으로 여러 가지 구현을 시도하고 있습니다. 물론, 낮은 소수를 생성하는 가장 빠른 방법은 이미 가지고 있기 때문에 하드 디스크 프라임리스트 데이터 파일을 설정하려고합니다. 나는 소수를 생성하는 모든 코드를 작성하고 싶지만 이미 만들어진 저장 방법을 사용하는 것에 대해서는 아무런 걱정이 없습니다. 나는 실제 코딩에 관해서는 거의 경험이 없지만 이론의 대부분을 이해하고있다.

그래서 내가 너희에게 몇 가지 질문을 가지고 (이 차라리 INT 변수보다, 수학 정수에 대해 이야기 할 것입니다 대부분의 점에 유의), 전문가들은 :

는

1) 순진 접근 방식은 바이너리 것 생성시 정수를 쓰십시오. 그러나, 내 머리 속에는 일종의 플래그로 구분 된 항목 목록이 상상되므로 32 비트보다 큰 정수를 저장할 수 있습니다 (그 점에 도달하면). 이것은 분명히 비효율적이지만 배열 [4723, 12782, 8357]의 원시 데이터가 4723F12782F8357처럼 보이는 것, 즉 숫자는 16 진수로 16 진수로 저장되고 F로 구분됩니다. 분명히 ABCDE 자릿수 가능성에 대한 데이터는 사용되지 않을 것이므로 매우 효율적인 시스템은 아니지만 내가 의미하는 바를 알 수 있습니다. 고정 길이 시스템에서 가장 작은 항목은 최대 크기 여야하므로 숫자가 길어질수록 더 많은 의미를 갖게됩니다. 나는 이미 C 또는 C++로 작성된 무언가가있을 것이라고 확신한다.

2) 또 다른 가능성은 길이 선언 시스템입니다. 여기서 각 정수가 저장되기 전에 고정 길이 (1 바이트라고도 함) 데이터의 정수가 선언됩니다 (비트 단위). 이는 분명히 이전 옵션과 비슷한 이점을 제공하며, 숫자 가능성을 낭비하지 않는 보너스가 추가되었습니다.

이런 종류의 데이터를 저장하는 방법에 대해 알고있는 사람이 있습니까? 크기 제한이 없도록 소수를 저장할 수있는 변수 유형이 있습니까? 더 좋은 방법은 간단한 정수 목록을 하드 디스크에 쉽게 검색 할 수있는 형식으로 저장하는 가장 효율적인 방법은 무엇입니까?

Answer 1

바퀴를 재발 명하지 마십시오. 큰 소수를 다루는 경우 GMP (http://gmplib.org/)와 같은 BigNum 라이브러리가 거의 필요합니다. GMP BigNum에는 직렬화 방법이 있으므로 디스크에 쉽게 쓰고 디스크에서 읽을 수 있으므로 알고리즘에 대해 자유롭게 생각할 수 있습니다. 우분투의 g ++ 컴파일러를 사용

Answer 2

는 I 긴 INT 32 비트임을 발견 긴 긴 INT 64

I 긴 INT의 길이 배열 변화의 수치를 들고, 공지 메르 센 소수의 완전 수를 산출 하였다; 즉 긴 곱셈, 긴 나눗셈 등을 할 때 스크래치 변수에 긴 long int를 사용할 수 있다는 것을 의미합니다. 또한 각 long의 값을 999,999,999 이상으로 제한하여 대답을 인쇄하기 쉽습니다.