오늘 할 일
- (완료) 알고리즘 시험
- (완료)소수문제
- (완료)노트 교과서읽기
1. 소수찾기 문제
https://school.programmers.co.kr/learn/courses/30/lessons/12921
소수라고 하면 1과 자신의 숫자로만 나누어 떨어지는 수 이다. 그리고 1은 소수가 아니다.
우선 자연수 n을 입력받아 1부터 n까지의 수들 중 소수의 갯수를 구하는 문제이다.
처음 접근법은 반복문을 돌려서 입력받은 n까지 나누어지는 수i를 만들어줄 것이고,
그 안에 반복문을 하나 더 n까지 나누는 수j를 만들어줬다.
i를 j로 나눴을때 나눠 떨어지는(나머지가 0이 되는) 수는 약수인데, 이게 1과 자기자신만 존재하기 때문에 약수가 2개가 될 수 밖에 없다. 그래서 약수가 되는 count를 만들어줬다.
그리고 만약 2개라면 소수이기 때문에 소수를 담으려고 미리 만들어준 빈 배열 arr에 push를 했다. 그리고 arr의 갯수를 출력하면 소수의 갯수를 알 수 있었다.
근데 여기서 문제 발생. 반복문을 돌고 나오면 count가 초기화가 되어버려서 기껏 구해놨던 count가 초기화되어 arr에 값이 들어가지 않는다.
count 초기화하는 부분의 스코프를 변경해줬더니 잘 실행이 되었다.
나누어지는 수인 i가 바뀌면 count를 초기화해줘야하는데 내부에서 계속 count값이 자꾸 더해지는 현상이 발생한다. 그래서 count는 2가 아니게되어 arr에 들어가지 못한다.
오류는 해결했지만, 정확성 테스트 일부와 효율성 테스트를 통과하지 못했다.
그러다가 발견한 에라토스테네스의 체.
에라토스테네의 체가 무엇인고 하면, 모래를 체에 거르듯 소수를 찾는 방법이다.
어떻게 거르냐면 아래와 같다.
2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
그리고 저렇게 구하는 방법도 있고, 수가 커지면 연산도 그만큼 늘어나니 제곱근을 구해서 해결하는 방법도 있다. 무슨 말인고 하면, 예를 들어 n이란 숫자가 있다고 하자. 그럼 1부터 n까지의 범위 안에 무수한 소수들이 존재할텐데 1부터 n까지의 범위를 반으로 싹! 나누면 소수의 절반이 나온다. 그 절반들은 완전한 제곱의 숫자(16, 25...)가 아니면 갯수가 짝수로 나와서 페어를 이룬다.(1,2,3,5,7,10과 같이) 그러므로 n의 제곱근까지의 범위를 구하면 소수를 빠른 시간안에 구할 수 있는 것이다.
예)
11^2 > 120일 때 =>11^2>120이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.`
