Suhwanc

프로그래밍 입문 수업 - 소수 판별법

기업 코딩 테스트 2~3번 단골 문제 중 하나인 N 이하의 소수(prime number)를 모두 찾아내는 방법에 대해 알아봅시다! 이 문제 유형은 대체로 백준 실버 1~2에 포진되어 있고 "문제는 어려우나, 이론은 간단한" 유형에 속합니다. (백준 1929 소수 구하기 : https://www.acmicpc.net/problem/1929) 이 유형은 "에라토스테네스의 체" 알고리즘을 알면 풀 수 있고, 모르면 못 푸는 문제인데요 에라토스테네스의 체란 고운 가루는 체에 걸러 통과시킨다는 뜻을 가지고 있는데, 여기서 고운 가루는 소수를 의미하게 됩니다. (이때 소수란 1과 자기 자신만 약수로 가지는 수를 의미합니다!) 에라토스테네스의 체에 대해서는 천천히 알아보고, 우선 일반적인 방법부터 살펴볼게요. 1) ..