댄지로그

Project Euler 7번 그리고 화려한 복귀! 본문

IT/Project Euler

Project Euler 7번 그리고 화려한 복귀!

댄지 홍영준 2017.08.03 13:02
친구들 오랜만이야! 잠시 쉬는 시간을 가지고 돌아온 댄지야

이럴 시간 없고 빨리 시작해보자! 오늘은 Project Euler 7번 문제를 풀 시간이야


10,001번째의 소수를 구하세요.

우리는 오늘 2, 3, 5, 7, 11, ... 으로 이어지는 소수들 중에서 10,001번째 소수를 구하여야 해.

즉 1하고 자기자신으로만 나누어지는 수를 찾아내는 코드를 짜면 되는 것이지!


자 내가 짠 C코드는 밑과 같아.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
int main(void)
{
    int i=0, j=0;
 
    int Count = 0;
    i = 2;  // 소수는 2부터 시작함
    while (Count != 10001
    {
        j = 2// j도 2부터 시작하여 나눠줌
        while (j <= i - 1)  // j가 i-1보다 작거나 같을 때
        {
            if (i % j == 0)  // i와 j를 나눈 나머지가 0인 경우
            {
                break;  // 반복문 탈출
            }
            j++;
        }
        if (i == j) // i와 j가 같은 경우
       {
            Count++// count에 1을 더함
        }
        i++// i에 1을 더함
    }
    printf("%d ", i);
    return 0;
}
cs


변수 i는 소수를 저장하기 위한 변수고 j는 소수를 판별하기 위해서 나눠줄 수를 저장하기 위한 변수야. 변수 Count는 10,001번째를 판별해줄 친구야.


i와 j를 나눌 때 자기 자신보다 작은 수로 나누어졌을 때에는 반복문을 탈출하고 i와 j가 같아서 나누어 떨어진다면 소수가 되는 거니깐 변수 Count에 소수 개수가 1개가 늘었으니 1을 더하게 되는거지.


이 과정을 반복하여 최종 결과인 '104743'이 나오게 돼


17. 8. 3 'Project Euler 7번 그리고 화려한 복귀!' 끗

0 Comments
댓글쓰기 폼