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

문제 설명

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

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

 

문제 풀이

2부터  n의 제곱근까지 나눠줬을 때 나머지가 0이 아니면 소수입니다

 

풀이 코드

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

 

<출처>

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

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