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.0107 sec