E D R , A S I H C RSS

소수구하기

문제 정� 1

문제제기

~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; 
}
결과는 다�과 같다.
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.0068 sec