[Silver4] No.01978 소수찾기
01 Mar 2022소수찾기
문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
풀이
해당 문제를 풀려면 먼저 소수의 정의를 알고있어야 한다. 먼저 소수란 1을 제외하고 1과 자기 자신의 수로만 나누어 떨어지는 수를 말한다. 소수를 구하는 방법은 여러가지 방법이 있다.
x미만의 값으로 나누어 소수찾기
간단하게 예를들어 풀이하자면 N개의 주어진 수 중에서 첫번째의 수를 x이라고 하자. x미만의 자연수로 x을 나누었을 시 나머지가 0인 수가 나오면 x이라는 수는 소수가 아니라는 뜻이다. 해당 예시로 4는 4미만의 수인 2로 나누었을 시 나머지가 0이 되므로 소수가 아니게 된다.
제곱근을 이용한 소수찾기
제곱근은 주어진 x의 값이 있을 때 제곱해서 x가 되는 값을 제곱근이라고 한다. x의 값이 15라고 하자. 15의 제곱근은 3.87xx.. 이고, 해당 정수를 가져오면 3이라고 볼 수 있다. 하지만 여기서 의문이 생긴다. 왜 제곱근이하의 수로만 판별이 가능한지? 15값의 약수는 1, 3, 5, 15이고, 1 * 15, 3 * 5, 5 * 3, 15 * 1의 해당 계산을 통해 구할 수 있다. 15의 값을 구하기 위한 계산의 경우 1 * 15, 3 * 5와 5 * 3, 15 * 1 처럼 대칭 이고, 제곱근인 3.87의 경우 1 * 15, 3 * 5, 제곱근 3.87xx , 5 * 3, 15 * 1로 볼 수 있기 때문에 약수의 수를 절반으로 줄여 준다고 생각하면 된다.
에라토스테네스의 체
에라토스테네스의 체는 아래의 글에서 확인 할 수 있다.
간단하게 설명하자면 1 부터 N까지의 수를 체로 거르듯 소수를 찾는 방법라하여 에라토스테네스의 체라고 한다.
풀이 소스
첫번째 방법으로는 1부터 N까지의 수로 나누어 소수를 찾는 방법이다.
두번째 방법으로는 제곱근을 이용해 소수를 구하는 방식이다.