E D R , A S I H C RSS

소수구하기

문제 정의 1

문제제기

~cpp 
정말 정말 급한건데요
100억의 소수 즉 11자리 소수를 구하는 프로그램이나
11자리 소수 어떤것이 있는지 알려주세요
제 컴으론 계산이 안되는데
님들아 제발 구해주세요^^
답변 기다리겠습니다 
꾸벅...

누군가 자유게시판에 다음과 같은 문제를 질문을 했다. 글이야 기분나쁘지만, NeoCoin은 이것이 pc로 가능한가가 궁금해 졌다.

문제를 이렇게 정의했다.
{{|
11자리로된 모든 소수 구하기.
|}}

----
문제정의 150000이하 소수를 구하는 소스중 남훈이의 소스에서 제곱근 연산을 넣고, 모든 인자를 static, 컴파일러 옵션을 최대로해서 돌렸다. 출력은 필요 없으므로, 시간과 갯수만 출력한다. (Duron 800 MS VS.NET 2003)
소스는 이것이고,
~cpp 
#include <stdio.h> 
#include <time.h> 
#include <math.h>

#define DECIMAL 10000
#define MAX_PRIME 5*DECIMAL

static int primeArr[1*DECIMAL] = {2, }; 
static int i, j, flag, primeArr_p, limit, count = 0;   
static time_t start, end;          

int main(void) {
    primeArr_p = 1;

	start = clock();
    for (i = 3; i < MAX_PRIME; i += 2) { 
		limit = (int)sqrt((double)i);
		flag = true;
        for (j = 0;primeArr[j] <= limit;j++){ 
			if (i % primeArr[j] == 0) { 
				flag = false; 
				break;
			} 
        } 
        if (flag)
			primeArr[primeArr_p++] = i;        
    }    
    end = clock(); 

	printf("%d 이하 소수n",MAX_PRIME);
	printf("%f 초n", (double)(end - start) / CLK_TCK); 
	printf("소수 %d 개 발견n",primeArr_p);
    return 0; 
}
결과는 다음과 같다.
prime_50000.JPG prime_500000.JPG prime_5000000.JPG prime_50000000.JPG
보다시피, 시간의 측면에서 50,000,000(5천만-8자리) 이후는 상상하기 싫다. 시간문제가 아니라 메모리 공간적인 문제도 존재할 것이다. 5천만 까지가 발견된 소수만 보관해도 (3001134*4)/(1000*1000)=12메가 정도 되니까 말이다. 앞으로 목표자리수인 3자리 동안 소수 갯수가 100배 증가하면 1.2 기가가 된다. :(

대체 11자리 모든 소수들을 구하려면, 어떻게 해야 할까요?
----
NumberTheory를 공부해라. --JuNe
마침 정수론을 보고 있었습니다. 허나 제시된 '임의의 큰수에 대한 소수 판정 방법'에서 위의 시공간의 문제를 줄여줄 여지가 보이지를 않내요. 저 문제 내준 사람은 어떻게 풀라는 궁금해요. 11자리라.. 좀더 생각해 봐야겠습니다. --NeoCoin
위 문제는 11자리 소수를 모두 구해라가 아니고 "11자리 소수를 구해라"일 것이다. --JuNe
----
723만자리짜리 소수가 발견되었다네요 관련기사 - 임인택
BBC의 방송 기사를 옮겨서 기사가 부실한것 같다. 관련내용 그리고 이해가 안가는게, 메르센 소수를 발견하는게 그 사람의 목표였는지, 아니면 발견된것이 메르센 소수인지도 이해가 안가게 해두었지. 것참 관심없는 내용이라고 저렇게 해둔건가.--NeoCoin
----
문제분류
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:30:13
Processing time 0.0266 sec