코딩테스트 연습 > 소수 찾기

 

 

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

프로그래머스

 

 

풀이 - 나의 생각

 

소수는 1과 자기 자신으로만 나누어지는 수입니다.

 

이걸 판별하는 여러가지 방법이 있는데

 

저는 trial division(시도로 나누기) 방법을 사용했습니다.

 

 n이 주어질때

 

2부터 n의 제곱근까지만 확인하면 되는겁니다.

 

예를 들어서

 

16이 주어질 때

 

2분터 4(16의 제곱근)까지만 나누어 보면

 

소수인지 아닌지 판별이 가능한 것을 알 수 있습니다.

 

코드

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i = 2; i <=n; i++){
            if(isPrimeNumber(i)) answer++;
        }
        return answer;
    }
    
    public static boolean isPrimeNumber(int num){
        if(num <= 1) return false;
        
        for(int i = 2; i <= Math.sqrt(num); i++){
            if(num%i == 0) return false;
        }
        
        return true;
    }
}

 

 

 

 

 

 

 

다음에 또 봐요