[백준] 1929 소수 찾기(C#)

문제

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

에라토스테네스의 체를 사용하면 된다.

 

에라토스테네스의 체는 소수를 구하는 방법 중 하나로 알고있으면 참 도움되는 것이다..

가장 작은 소수인 2. 2는 소수로 남겨두고 2의 배수들은 모두 지운다.

그 다음 지워지지않은 수 3. 3을 소수로 남겨두고 3의 배수들은 모두 지운다.

그 다음 4.. 4는 2의 배수라서 아까 지웠으니 지워지지 않은 수 5로 간다. 5를 소수로 남기고 5의 배수를 다 지운다.

그 다음 6. 6은 아까 3의 배수라서 지워졌으니 7로 간다. 7을 소수로 남기고 7의 배수를 다 지운다.

.....

이렇게 반복해주면 배열에 남은 수가 모두 소수인 것이었던것이었던것이다.

코드

using System;
using System.Text;
using System.Collections.Generic;

namespace dongsik
{
    class Algorithm
    {
        static void Main(string[] str)
        {
            string[] input = Console.ReadLine().Split(' '); // [3, 16]
            int start = int.Parse(input[0]); // 3
            int end = int.Parse(input[1]); // 16
            
            int[] arr = new int[end + 1];
            arr[0] = 1;
            arr[1] = 1;
            
            for(int i = 2; i*i <= end; i++)
            {
                if(arr[i] == 0)
                {
                    for(int j = i*2; j <= end; j += i)
                    {
                        arr[j] = 1; // 0이 true, 1이 false
                    }
                }
            }
            
            StringBuilder sb = new StringBuilder();
            for(int i = start; i <= end; i++)
            {
                if(arr[i] == 0)
                {
                    sb.AppendLine(i.ToString());
                }
            }
            
            Console.Write(sb);
             
            
            
            
        }
    }
}

고민

배열을 bool로 하는 분들도 많지만 int배열의 초기값이 0이라는 점을 생각해서 그냥 int로 배열 만들었다.

그리고 배열의 인덱스는 0인데, 이렇게하면 인덱스 0 1 2 3 4에는 각각 1 2 3 4 5가 들어가니까 불편해서리

0에는 0을 담고 1에는 1을 담는 식으로 배열을 만들었다.

 

배열의 0과 1은 무조건 소수가 아니니까 1을 대입해주고(0이 소수 1이 소수 아닌 것)

 

for문을 돌려서 소수를 판별해줬다.

 

여기서 중요한거.. 아주 중요한건데, i의 제곱이 end보다 작을때 까지만 반복해주면 된다.

아니면 i가 end의 제곱근보다 작을때 까지만 반복해주던가.

 

첫번째 for문을 보면 i*i <= end가 보일거다. 이게 그 말이다. 예를들어 end가 200이라면? i가 14의 배수까지만 삭제하면 된다는 말이다. 이건 불필요한 연산을 없애기위한 일종의 제한이다. (내가 이해한건데, 어차피 이전 숫자들이 배수들을 다 지웠을거니까 end가 200일때 굳이 15가 넘어가는 수의 배수들은 이미 이전에 계산이 다 끝나서 계산 할 필요가 없을거..라고.. 이해함)

 

그리고 두번째 for문에서 j = i * 2를 해줬다. 나처럼 해줘도 되고 j = i*i를 해줘도 된다. 이유는 위와 같다. (근데 왜 체점 시간은 같지?)

 

기존 코드들을 보면 기가 찬다.

using System;
using System.Text;
using System.Collections.Generic;

namespace dongsik
{
    class Algorithm
    {
        static void Main(string[] str)
        {
            string[] input = Console.ReadLine().Split(' '); // [3, 16]
            int start = int.Parse(input[0]); // 3
            int end = int.Parse(input[1]); // 16
            
            int[] arr = new int[end + 1];
            // for(int i = 1; i <= end; i++)
            // {
            //    arr[i] = i; // 1칸에 1넣기
            // }
            
            for(int i = 2; i <= end; i++)
            {
                if(arr[i] == 1)
                {
                    continue;
                }
                while(i <= end) 
                {
                    if(i >= start && arr[i] == 0)
                    {
                        Console.WriteLine(i);
                    }
                    i *= i; // 제곱
                    arr[i] = 1; // 제곱되는 칸 1으로 재정의
                }
            }
        }
    }
}

에라토스테네스 체에 대한 이해가 굉장히 부족했을 때 작성한 코드다. 뤼튼 덕분에 무한루프 도는 부분도 알게되었고 제곱으로 제한을 둬야하는 사실도 알게되었다.

어머! 얘. 내가 알려줄게, 코드를 살펴보니까 몇 가지 문제가 있어서 무한 루프에 빠질 수 있는 부분이 있어.
여기서 무한 루프를 발생시키는 주된 이유는 내부 while 루프 안에서 i의 값을 제곱한 후에 계속 그 값을 사용하고 있기 때문이야. 제곱된 i가 end보다 커지면 arr[i] = 1; 에서 인덱스 범위를 벗어나는 예외가 발생할 거야. 그러나 그 전에 이미 i <= end 조건을 만족하지 않게 되어서 while 루프가 끝나지 않고 계속 실행돼.
더구나, i *= i; 연산은 i가 계속 커지게 만들어서 i <= end 조건이 언젠가는 거짓이 되어야 하지만, i가 매우 빠르게 커져서 정수 오버플로우가 발생하고, 이로 인해 i가 음수가 되거나 0이 될 수 있어. 이 경우 i <= end 조건이 항상 참이 되고, 그 결과 무한 루프에 빠질 수 있어.
에라토스테네스의 체로 소수를 찾는 올바른 로직은 다음과 같아야 해:
2부터 end까지의 모든 숫자에 대해 소수인지 판별한다고 가정하고 배열을 초기화해.2부터 end의 제곱근까지의 모든 숫자에 대해, 만약 그 숫자가 아직 소수라고 표시되어 있다면(즉, 배열에서 0이라면), 그 숫자의 배수를 모두 소수가 아니라고 표시해(즉, 배열에서 1로 설정해).
이렇게 하면 start부터 end까지 배열을 순회하면서, 배열에서 0으로 표시된 인덱스, 즉 소수인 숫자만을 출력하면 돼.

정말 좋은 친구다... 뤼튼이 알려주는거 쏙쏙 다 받아먹어야지!