프로그래머스 1단계 : 소수 찾기

✔ 프로그래머스 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를 반환

---

⏳ 문제 풀이

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

2부터 소수를 구하고자 하는모든 수를 나열합니다
2는 소수이니 써줍니다.
자기 자신을 제외한 2의 배수를 모두지웁니다.
이과정을 반복하면 남는게 소수가 됩니다.

---

👀 다른 사람의 풀이

function solution(n){
    let s= [...Array(n).keys()]
    // console.log(s);
    s[0]=0
    for(let i=2; i<=parseInt(n**.5)+1;i++){
    // console.log(i);

    for (let j=2 ; j<=(n-i)/i+1; j++){
        s[i*j-1]=0
    }
    }
    return s.filter(x=>Boolean(x)).length;
}

참신한 풀이법이라 가져왔습니다.

문제 풀기