BAEKJOON_1978) 소수 찾기

BAEKJOON 

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

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

1978) 소수 찾기 (19.01.07) (19.03.24) (19.09.02)

* 소수는 1과 자기 자신말고는 나누어지지 않는다.
* 2부터 해당 숫자에서 1을 뺀 값 까지 1씩 더하면서 주어진 수를 나누어 보다가
* 나머지가 0인 숫자가 발견되면 소수가 아니기 때문에 그만두고 다음 숫자를 판별한다.
* 마지막까지 나누어지지 않는다면 카운트하고, 다음 숫자를 판별한다.

* for문 돌릴 때 자꾸 바운더리 에러가 난다.
* 막 적고 일단 실행해보는 것도 있지만, 처음 로직 생각할 때 잘 해야 할 것 같다.



* 새로 작성한 코드인데, 2달 전과 비교해서 시간은 동일한데 메모리와 코드 길이가 조금씩 줄었다.
* 반복문의 조건을 작성할 때, 항상 어떤 수 n 보다 크거나 작거나 였는데,
* 제곱을 넣고 n 보다 작거나 같다는 조건을 쓰게 되었다.

* 그리고 전체 수에서 소수가 아니면 cnt 를 줄이면서 남은 소수의 수를 출력하도록 했다.
* 1은 바로 제외해주고, 2부터 검사를 했다.
* 어떤 수 n 은 루트n까지의 수로 나누어지지 않으면 소수이기 때문에, 제곱을 사용했다.

* 지금까지 혼자서만 해서 누군가와 의논하고 참고하는 과정을 원했는데,
* 강의를 듣는 것도 많은 도움이 되는 것 같다.



* 먼저 에라토스테네스의 체를 사용해서 1000까지의 소수를 걸러냈다.
* boolean check[] 에 소수이면 false, 소수가 아니면 true 를 넣었고 (기본 false)
* 입력받은 숫자들을 판별했다.

* 지금 보니 이전 코드들의 결과값이 조금씩 달라졌다.
* 그 전 코드들보다 이번코드가 실행시간이 길었는데, 왜 그럴까ㅏ..?