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

1. 문제

---

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

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

 

제한 조건

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

입출력 예

n	result
10	4
5	3

입출력 예 설명

 

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

 

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

 

 

 

2. 문제 정리

---

• 숫자 n이 주어졌을 때 2부터 n까지 수 중 소수의 수는??
• 해당 숫자가 소수인지 판단하는 메서드를 만들자.
• 소수의 정의는 1과 자신을 제외한 다른 약수는 없는 수 이다.
• 그렇다면 2부터 n-1까지 모두 나눠서 나머지를 확인해 보면 될까???
• 그렇게 하기에는 너무 느리다.
• 그렇다면 나머지를 확인하는 범위를 어디까지 정해야 할까?
• 바로 제곱근 까지 보면 된다.
• 어떤 수의 약수라는 것은 결국 작은 수 & 큰 수 의 조합으로 이루어 진다.
• 작은 수의 범위만 정해주면 된다.
• 그렇다면 가장 큰 작은수는 뭘까?
• 작은수가 커지고 큰 수가 작아지면 결국 같아진다. 즉 제곱근이다.
• 따라서 2부터 제곱근 까지의 수로 나누었을 때 나머지를 확인하면된다.
• 또한 중요한 사실은 2를 제외하고 소수에는 짝수가 없다.
• 따라서 짝수는 확인할 필요가 없다.
• 그러므로 해당 수가 소수인지 판단할 때도 짝수로 나누어 볼 필요가 없다.

 

 

3. 코드

---

 

class Solution {
    public int solution(int n) {
        int answer = 1; // 2 반영

        for (int i=3; i<=n; i=i+2){
            if (isPrime(i)) answer++;
        }
        return answer;
    }

    private boolean isPrime(int number) {

        for (int i=3; i<=Math.sqrt(number); i=i+2){
            if ((number%i) == 0){
                return false;
            }
        }
        return true;
    }
}

 

 

4. GitHub : 211213 Find PrimeNumber

---

GitHub - bsh6463/coding_test