소수구하기

[edit]

문제 정의 1 ¶

50000 이하의 모든 소수를 구한다. 추천 목표시간은 1초 이내입니다.

소수구하기/재니

----

[edit]

문제제기 ¶

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

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

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

----
문제정의 1의 50000이하 소수를 구하는 소스중 남훈이의 소스에서 제곱근 연산을 넣고, 모든 인자를 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; 
}

결과는 다음과 같다.

보다시피, 시간의 측면에서 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

----
문제분류