[프로그래머스] 소수 찾기 (java)

💁‍♀️  문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

문제를 열심히 풀던 상빈이는 일반화된 콜라 문제를 생각했습니다. 이 문제는 빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산하는 문제입니다. 기존 콜라 문제와 마찬가지로, 보유 중인 빈 병이 a개 미만이면, 추가적으로 빈 병을 받을 순 없습니다. 상빈이는 열심히 고심했지만, 일반화된 콜라 문제의 답을 찾을 수 없었습니다. 상빈이를 도와, 일반화된 콜라 문제를 해결하는 프로그램을 만들어 주세요.

콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다. 상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.

❌ 제한사항

• n은 2이상 1000000이하의 자연수입니다.

 

 

💡  입출력 예

 

 

입출력 예 #1

• 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2

• 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

👩 내 풀이

public int solution(int n) {
     int answer = 0;
     for(int i=2; i<=n; i++){
         boolean flag = true;
         for(int j=2; j<=Math.sqrt(i); j++) {
        	 if(i%j == 0)  { //나누어떨어지면 소수X
        	   flag = false; //falg를 false로 바꿔서 소수가 아니라고 체크
                   break; //break를 안해주면 효율성 테스트 통과 못함
        	  } 
           }
      if(flag==true) //소수인 숫자는 flag가 변하지 않고 true 
         answer++; 
    }
   return answer;
}