[Java] 자연수 n 이내의 소수 개수 출력하기

자연수를 입력받고 1부터 n(2<=n<=200000)까지 사이의 소수 개수를 출력해라.

제한시간 1초.

 

자연수 20이면

소수 2, 3, 5, 7, 11, 13, 17, 19

 

입력예제 

 

20

 

출력예제 

 

8

 

 

💡 1. 내 풀이 정리

---

 

처음 문제를 봤을때 나머지 연산자(%)를 사용해야겠다 라는 생각까지는 했었다.

그리고 바로 문제 풀이를 시작했다.

자연수 숫자를 입력받고 solution 메서드로 넘겨준다.

일단 입력받은 자연수에서 1을 제왜해서 시작해야하고 자연수 포함해서 소수여부를 확인하는거니까

첫 for 문은 2 부터 자연수num 을 포함한 범위로 설정했다.

이후 각 자연수 내부에서 정보를 습득할 cnt 를 선언해주고

for 문을 하나 더 선언해준다.

여기서 for 문은 외부 for문에서 돌고있는 자연수보다 작은 수만큼 설정해서

자연수 i 에서 1부터 자연수보다 작은 j 를 나눴을 때 1이 포함되므로

소수라면 나눴을때 나머지가 0 이 나온경우는 한번일 것이다.

 

그래서 cnt가 1일때 반환할 answer에 1씩 더해줬다.

 

난 여기서 2중 포문을 돌렸는데 문제에 제한시간 1초라는 기준이 있었고 20만을 넣었을때 1초가 훨씬 지나서 결과가 나왔다. 다른 방법으로 풀었어야 했다.

71초 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ....

💡 2. 강사님 풀이

---

 

강사님은 에라토스 테네스 채? 를 이용해서 소수를 구했다.

강사님 코드로 만들어 봤는데... 0.006초 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

이중포문 비슷하게 쓰긴 하는데 이때 이중포문을 쓰는 경우를 조건문에 해당하는 경우에만

for문이 하나가 더 돌아가는 시스템이었다. 신기하다..

 

arr 에서 index의 값을 소수를 파악하기 위한 자연수로 설정하셨다.

그래서 arr 을 선언할 때

num+1 의 배열을 선언했다.

 

처음 배열은 선언하면 내부의 값을 따로 설정 안한경우에 모두 0 이 들어있다.

2부터 체크를 해서 arr[i]가 0 인경우 반환값을  1씩 올려주고

arr[i]가 0인 경우에만 이중 포문을 돌리는데

이때 i에서부터 설정한 자연수까지 i부터 i크기 만큼 거리를 두고 arr배열에 1을 넣어준다.

 

그러면 다음 arr[i]를 조회할때 1이 들어간 부분은 소수의 조건에서 벗어나 이중for문을 돌지 않는다.

이게 훨씬 효율적인 코드구나.. 크👍

 

 

 

코테 관련해서 많이 부담스러웠는데 강의를 통해 푸는 방법들을 배우니 이 시간이 즐겁습니다.

진짜 기능하나하나 다양한 방법으로 잘 가르쳐주십니다.

출처 : 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 대시보드 - 인프런 | 강의 (inflearn.com)