언유상씨의 건전한 취미생활

문제 이름 : 소수 찾기 문제 번호 : 1978 사용 언어 : C 문제 유형 : 완전 탐색 문제는 다음과 같다. 빈 배열을 만든 뒤 제시된 원소를 넣고 소수의 개수를 세면 된다. 이때 소수를 판별하는 방법으로는 두가지 방법을 같이 쓸 것이다. 1. 숫자가 2 또는 3인가? 2. 숫자 보다 작은 수들중 나눈 값의 나머지가 0인 수가 있는가? 2번 조건을 조금만 더 생각해보면 다음과 같은 결론에 도달할 수 있다. 소수가 아닌수는, 제곱근의 값을 중심으로 앞 뒤에 나누는 수가 존재한다는 것. 예를 들어보면 다음과 같다. 36 의 약수 - 1 2 3 4 6 9 12 18 36 제곱근인 6을 전후의 값을 곱한다는 것을 알 수 있다. 따라서 1부터 제곱근 값 사이에서 원래 수를 나눌 수 있는 수가 없다면, 그 수는..