섹션 2. Array(1, 2차원 배열)_5. 소수(에라토스테네스 체)

문제

• 자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
• 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

입력

• 첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

출력

• 첫 줄에 소수의 개수를 출력합니다.

입출력 예제

---

풀이 방식을 정리해보자.

 

1.  자연수 N을 입력받고, 메소드를 호출하는 코드를 작성한다.

 

2. 메소드 구현으로 넘어가보자.

 

3. 각 변수를 선언한다.

• 결과값을 저장할 변수 result를 선언한다.
• 0이면 소수, 1이면 소수가 아님을 표현할 배열 Arr[] 을 선언한다.

4. 2부터 N까지 도는 for문을 작성한다.

• 1부터 N까지의 자연수이기에 0은 들어가지 않고, 1은 소수가 아니기 때문에 2부터 시작한다.

5. 배열에 값이 0이면 소수이므로 결과값을 더해준다.

 

6. 또 다른 for문을 안에 작성하여, i의 배수만큼 돌며 배수가 있으면 배열에 1을 넣어준다.

• i가 2라면, 2라는 값은 맨 처음에 0이 들어가있기에 result에 1이 더해진다.
• 그 후에 j를 통해 2의 배수를 찾는다. 2의 배수라는 것은 소수가 아닌 것이기에 해당 값들에 1을 넣어준다.

수행 결과를 확인한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.