BAEKJOON_1929) 소수 구하기

BAEKJOON 

# 단계별 # 알고리즘 기초 # 2019 SW역량테스트준비-기초

#소수 구하기 # 수학 1 # 수학

1929) 소수 구하기 (19.01.17) (19.03.24) (19.09.02)

* 에라토스테네스의 체. 진짜 엄청 골치아팠다.
* 우선 배열의 길이는 가장 큰 숫자만큼, 배열의 각 칸에는 인덱스와 같은 넘버를 넣는다.
* 2의 제곱부터, 3제곱,,, 이렇게 cnt값을 설정해 주고, 그 값이 가장 큰 숫자보다 커지면 3의 제곱으로 넘어가게,
* 그렇지 않으면 배수가 되는 배열칸의 숫자를 0으로 만들어줬다.
* 여기서 1번칸을 따로 0을 만들어주지 않으면, 답 출력 시 1도 함께 나온다.
* 2의 배수부터 3, 4 로 가장 큰 숫자까지 돌고나서 종료된다



* 이게 제일 처음 제출했던 코드. 역시 시간초과에 걸렸다.
* 2는 소수이기 때문에, 반복문을 돌지않고 바로 출력.
* i가 3 이상이 되면, 2부터 i보다 작은 수들로 나누어보기.
* 나누어진다면 소수가 아니기 때문에, i를 증가.
* 나누어지지 않는 숫자중에  j가 i보다 1 작을때까지 판별했다면 소수이므로 출력.



* 분명 이클립스에서 정답이 나오는걸 확인했는데 시간 초과는 어떻게 해결해야할지 막막했다.
* 반복무을 수정하면서 경우의 수를 쳐냈는데도 해결하지 못했고,
* 결국 코드 전체를 수정했다.



* 위 코드를 살짝 정리.
* 이것도 시간초과. 뭐가 잘못된거지

* 강의를 듣고 다시 풀었다.
* 이전에 풀었던 답보다 시간과 코드길이가 살짝 줄었는데, 메모리는 증가했다.



* i 가 2 일때, j 는 4, 6, 8, 10 ...
* i 가 3 일때, j 는 6, 9, 12, 15 ...
* 이렇게 j에 해당하는 mn[j] 값이 0을 만들어주면
* i 가 t 일때, t*t 이전의 값들은 모두 0이 되어있는 상태이므로 j=t*t 부터 살펴보면 된다.
* 하지만 여기서 안쪽 for 문에 j를 i*2로 한 것은 i*i일 경우, 정수 범위가 넘어가기 때문이다.

* 그리고 마지막에 0으로 지운 수와 소수가 아닌 1을 제외하고 나머지를 출력하면 정답이다.

* 여기서 마지막 if 문의 조건을 수정해주었다.



* 시간과 메모리, 코드 길이 모두 조금 줄었다.



* 에라토스테네스의 체를 구현해서 풀었다.
* 시간이 조금 늘었지만 메모리가 줄어서 다행인....?