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

● 소수 찾기 알고리즘을 만들 수 있다.

문제 https://programmers.co.kr/learn/courses/30/lessons/12921

 

 

 

접근 방법

    /*
    1.입력값의 소수의 갯수 찾기
    2.for 2 , 나누기 0 나뉘면 소수 1을 제외한 1번
    3.1과 본인을 제외한 나누기가 되면 소수가 아니지
    4.소수만 찾아서 확인하면 소수
    */

2중 for문을 돌렸더니 효율성 체크에서 불합이 되었다.

보완으로 소수를 찾고 소수로만 2중 for문으로 개선을 하였다.

하지만 여전히 효율성측면에서는 불합이 되었다.

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        System.out.println(n);
        answer = process(n);
        return answer;
    }
    
    /*
    1.입력값의 소수의 갯수 찾기
    2.for 2 , 나누기 0 나뉘면 소수 1을 제외한 1번
    3.1과 본인을 제외한 나누기가 되면 소수가 아니지
    4.소수만 찾아서 확인하면 소수
    */
    public int process(int n){
        int result = 0;
        List<Integer> primeList = new ArrayList<Integer>();
        for (int i =2; i <= n ; i++ ){
            
            if(i == 2) primeList.add(2);
            boolean primeChk = true;
            for(int j =0; j<primeList.size() ; j++){
                if(i%primeList.get(j)==0){
                    primeChk = false;
                    break;
                }
            }
            if(primeChk){
                primeList.add(i);
            } 
        }
        result = primeList.size();
        return result;
    }
}

 

해결 솔루션

math.sqrt 제곱근을 사용하면 소수 찾는 모수를 줄일 수 있다.

자연수는 대칭으로 이루어져있기 때문에(에라토스테네스의 체) 접근법을 활용 

81의 소수를 찾는다면

81의 약수는 1, 3, 9, 27, 81

Math.sqrt(81) = 9

9를 기준으로 대칭으로 2개씩, 즉 제곱근까지 모수로 접근하면 모수를 줄여 속도를 높일 수 있음

 

class Solution {
  public int solution(int n) {
      int answer = 0;
      for(int i = 2; i <= n; i++){
          int j = 2;
          int cnt = 0;
          while(j <= (int)Math.sqrt(i)){
              if(i % j == 0){
                cnt += 1;
                break;
              } 
              j += 1;
          }
          if(cnt == 0) answer += 1;
      }
      return answer;
  }
}