[프로그래머스|Level.1] 소수 찾기

 

문제 설명

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

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

(1은 소수가 아닙니다.)

 

제한 사항

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

 

입출력 예

n	result
10	4
5	3

 

JavaScript

function solution(n) {
    var answer = 0;
    for(let i = n; i > 1; i--){
        if(i%2 === 0) continue;
        if(isPrime(i)) answer++;
    }
    return answer+1;
}

function isPrime(n){
    for(let i = 2; i*i <= n; i++){
        if(n%i == 0) return false;
    }
    return true;
}

 코드를 아무리 간결히 해도 효율성 검사를 충족할 수 없다.

에라토스테네스의 체 방식을 이용하고자 한다.

소수판별법

소수판별법 - 위키백과, 우리 모두의 백과사전

 

Python

def solution(n):
    solution = []
    arr = [1] * (n+1)
    arr[0], arr[1] = 0, 0
    for i in range(2, n+1):
        if arr[i]:
            solution.append(arr[i])
            for j in range(i, n+1, i):
                arr[j] = 0
    return len(solution)

JavaScript

function solution(n) {
    var answer = 1;
    var arr = new Array(n+1); 
    arr.fill(1);
    
    for(let i = 2; i <= n; i++){
        if(i%2 === 0) continue;
        if(arr[i] === 1){
            for(let j = i; i*j <= n; j++)
                arr[i*j] = 0;
            answer++;
        }
    }
    return answer;
}

C++

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 1;
    vector<bool> arr(n+1, true);

    for (int i=2; i<=n; i++) {
        if (i%2 == 0) continue;
        if (arr[i] == true) {
            for (int j=2; i*j<=n; j++) 
                arr[i*j] = false;
            answer++;
        }
    }

    return answer;
}