Profile
도개걸윷모

2018.08.14

2018-08-14 오랜만에 돌아온 기념 특집

조회 수 222 추천 수 1
애드블럭을 꺼주시면 서버 운영에 도움이 됩니다.
부탁드립니다.

안녕하세요 도개걸윷모입니다. 오늘은 소수에 관한 문제를 내볼 생각입니다

소수는 크게 2가지의 의미가 있습니다.

1.25, 0.51, 3.14 같이 소숫짐이 있는 소수와

2, 3, 5, 7, 11....이런 자기 자신과 1 외에는 나눠지지 않는 소수로 나눌 수 있지만, 

저는 후자에 관하여 이야기를 하겠습니다.

 

1~n까지의 모든 소수를 찾는 방법으로는 에라토스테네스가 매우 유명합니다.

체로 치듯이 수를 제외시키기 때문에 에라토스테네스의 체라고도 불리기도 합니다.

과정은 다음과 같습니다.

 

 

1. 원하는 범위(이 경우에서는 n까지)만큼 자연수를 나열한다

 

2. 0은 자연수가 아니고, 1은 소수도, 합성수도 아니니 1을 제일 먼저 제외시킨다.

 

3. 먼저 2를 소수로 표기하고, 2를 제외한 2의 배수들을 모두 제외시킨다

 

4. 그 다음 3을 소수로 표기하고, 3을 제외한 3의 배수들을 모두 제외시킨다.

 

5. 그 다음 5를 소수로 표기하고, 5를 제외한 5의 배수들을 제외시킨다.

 

6. 소수들을 이렇게 계속 제외시킨다.

 

7. 다음 소수가 만약에 n보다 크면 과정을 끝내고 제외되지 않은 수들이 소수가 된다.

 

 

2324F43E5246ED5A2D.gif

 

 

위의 알고리즘 말고도 많은 알고리즘이 있습니다.

예시로는 k번째 수가 2부터 k-1까지의 수들로 나눠지는 확인하면서 수가 소수인지 확인하는 방법입니다.

사실 이 말고도 수없이 많은 방법들이 존재합니다. 

 

위의 알고리즘들 중 두 번째 알고리즘을 gml로 옮기면 다음과 같습니다

 

for(i=2;i<=n;i++)
{
    check=0;
    for (j=2;j<=i-1;j++)
    {
         if (i%j==0)
             check=1;
    }
    if check==0
         a[array_length_1d(a)]=i;
}

 

 

위의 함수는 2부터 n까지의 수들이 자신 보다 작은 숫자들에게 나누어 떨어지는지 일일이 확인하면서 소수인지 판별하는 알고리즘을 이용한 코드입니다. 말그대로 위에 적어둔 알고리즘 중 2번 째 것이지요.

하지만 위의 코드는 또다시 최적화 될 수 있습니다.

 

 

for (j=2;j*j<=i;j++)
{
     if i%j==0
           check=1;
}
//.....

위에 코드의 4번째 줄을 이렇게 적을 시 어마어마한 량의 작업이 생략될 수 있습니다.

 

 

지금 왜 소수 알고리즘만 설명하고 오늘의 문제는 설명하지 않는지 궁금하시는 분도 계실텐데 제목을 보시면 아시다시피 이번 문제는 특집이여서 기한이 오늘까지가 아닙니다.

 

 

 

8월 19일 23시 59분 59초까지 즉, 일요일 밤까지 댓글로 적은 코드를 내신다면 제가 직접 컴파일을 해봐서

각각의 코드 중 컴파일 속도를 기준으로 등수를 정해 쿠키 보상을 줄 예정입니다.

쿠키 보상은 여태까지 보상들보다 클 예정이며, 이는 관리자님과 함께 상의해서 정할 예정입니다.

코드는 반드시 다음 조건을 만족하여야 합니다.

 

 

1.  1부터 n까지의 모든 소수를 구할 수 있는 코드여야 합니다.

 

2.  구한 소수들을 리스트나 배열에 담으셔야 합니다. (리스트와 배열 중 더 편하시거나 더 빠를 거라고 생각하시는 걸 이용하시면 됩니다)

 

3. GML로 짜야 하며, 몇번째 버젼인지 명확하게 표현해주셔야 합니다.

 

모두들 코딩 열심히 하시길 빕니다. 좋은 결과 나오길 빌겠습니다.

자기가 짜신 코드들은 비밀 댓글로 달아주시면 되겠습니다. 감사합니다.

 

추천해주신 분들



Profile
8
Lv

6개의 댓글

Profile
바람냥
2018.08.15
비밀글입니다.

비밀번호를 입력하세요.

Profile
잇창명
2018.08.15
비밀글입니다.

비밀번호를 입력하세요.

Profile
CoRin
2018.08.16
비밀글입니다.

비밀번호를 입력하세요.

Profile
겨울날
2018.08.17
비밀글입니다.

비밀번호를 입력하세요.

Profile
잇창명
2018.09.05
비밀글입니다.

비밀번호를 입력하세요.

Profile
에디터
번호 제목 글쓴이 날짜 조회 수
24 [GML | 제 2 회] 스프라이트와 오브젝트? 5 profile 며르치 2019.02.13 30
23 [GML | 제 1 회] 변수와 데이터 구조? profile 며르치 2019.02.09 35
22 오늘의 문제 1 2 부덩 2019.01.27 26
21 2018-12-02 오늘의 문제 #18 2 profile 도개걸윷모 2018.12.02 55
20 2018-11-28 오늘의 문제 #17 4 profile 도개걸윷모 2018.11.28 37
2018-08-14 오랜만에 돌아온 기념 특집 6 profile 도개걸윷모 2018.08.14 222
18 2018-06-16 오늘의 문제 #15 1 profile 도개걸윷모 2018.06.17 72
17 2018-03-02 오늘의 문제 #14 1 profile 도개걸윷모 2018.03.02 53
16 2018-03-01오늘의 문제 #13 3 profile 도개걸윷모 2018.03.01 49
15 2018-02-28 정답 공개 profile 도개걸윷모 2018.03.01 48
14 2018-02-27 오늘의 문제 #12 5 profile 도개걸윷모 2018.02.27 39
13 2018-02-26 오늘의 문제 #11 4 profile 도개걸윷모 2018.02.27 28
12 앞으로의 오늘의 문제 게시판 스케쥴 profile 도개걸윷모 2018.02.27 30
11 2018-02-25 오늘의 문제 #10 3 profile 도개걸윷모 2018.02.25 33
10 2018-02-24 오늘의 문제 #9 1 profile 도개걸윷모 2018.02.24 37
9 2018-02-23 오늘의 문제 #8 profile 도개걸윷모 2018.02.23 41
8 2018-02-22 오늘의 문제 #7 profile 도개걸윷모 2018.02.22 50
7 2018-02-21 오늘의 문제 #6 1 profile 도개걸윷모 2018.02.21 40
6 2018-02-20 오늘의 문제 #5 7 profile 도개걸윷모 2018.02.21 41
5 2018-02-19 오늘의 문제 #4 9 profile 도개걸윷모 2018.02.19 50

알림!

알림!X

메세지 테스트!
서버에 요청 중입니다. 잠시만 기다려 주십시오...