[프로그래머스/파이썬/자바] 소수 찾기

출처

---

문제 & 제한사항 & 예제

문제 설명

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를 반환

---

풀이

<start부터 end까지의 수 중 소수 구하기>

​

※아래 설명 코드는 자바로 설명했습니다.

 

1. 기본 방법

start부터 end까지 수를 살펴본다. (i 인덱스)

해당 값을 2부터 i-1까지의 수를 나눠보며 나눠지면 합성수, 끝까지 안 나눠지면 소수로 판단한다.

시간 복잡도는 n**2

class Solution {

public int solution(int start, int end) {

    int sw = 1;

    for(int i = start; i <= end; i++){

        sw = 1;

        if(i == 1){

            sw = 0;

            continue;

        }

        for(int j = 2; j < i ; j++){

            if(i%j == 0){

                sw = 0;

                break;

            }

        }

        if(sw == 1){

            System.out.println(i);

        }

    }

}

}

​

2. 제곱 근 이용

1번 방법과의 차이점은 j를 2부터 i-1까지의 수가 아닌 2부터 루트 j까지만 살펴보며 소수인지를 판단한다.

class Solution {

    public int solution(int start, int end) {

        int sw = 1;

        for(int i = start; i <= end; i++){

            sw = 1;

            if(i == 1){

                sw = 0;

                continue;

            }

            int root = (int) Math.sqrt(i)+1;

            for(int j = 2; j < root ; j++){

                if(i%j == 0){

                   sw = 0;

                   break;

               }

            }

            if(sw == 1){

                System.out.println(i);

            }

    }

}

​

3. 에라토스테네스의 체

2부터 end까지 살펴보면서 각각의 해당 수의 배수를 지워가는 방식이다.

class Solution {
    public int solution(int start, int end) {
        boolean visited[] = new boolean[end+1];
        for(int i = 2; i <= end; i++){
            visited[i] = true;
        }
        for(int i = 2; i <= end; i++){
            if(visited[i] == false){
                continue;
            }else{
                for(int j = i*2; j <= end ; j+=i){
                    visited[j] = false;
                }
            }
        }
        for(int i = 2; i <= end; i++){
            if(visited[i]){
                System.out.println(i);
            }
        }
    }
}

코드