소수 찾는 법

function solution(n) {

let prime = [];

for(let i = 2; i <= n ; i++) {

let isPrime = true;

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

if(i%j === 0){

isPrime = false;

break;}}

 if(isPrime) {

     prime.push(i)}

    isPrime = true

}

    return prime.length

}

문제는 이렇다.

주어진 숫자 내에 포함된 소수의 갯수를 구하여라.

 

그래서 내가 생각한 방법은 2부터 1씩 더하면서 주어진 숫자까지 하나하나 검사하는 방식이다.

소수는 1과 자기자신 외에 다른 수로 나눠질 수 없는 수를 의미하므로

for문을 2개로 감싸서 동작하게끔 했다.

 

이렇게 작성한 코드를 동작했더니,

테스트코드와 문제 7번정도는 성공한 것 같았다.

그 이후 효율성과 8,9,10번은 시간초과가 걸렸다.

 

제한사항으로 주어진 숫자는 2부터 1000000사이의 숫자였는데

아마 숫자가 너무 커지면 for문을 돌리는데 시간이 초과된 것 같았다.

 

그래서 구글링을 좀 했더니 숫자의 제곱근으로 나누어도 약수를 알아낼 수 있다는 글을 읽었다.

https://freedeveloper.tistory.com/391

[이것이 코딩 테스트다 with Python] 37강 소수 판별 알고리즘

위 블로그에서 해당 내용을 캐치하여 코드를 개선했다.

 

function solution(n) {

let prime = [];

for(let i = 2; i <= n ; i++) {

let isPrime = true;

for(let j = 2 ; j<= Math.sqrt(i) ; j++) {

if(i%j === 0){

isPrime = false;

break;}}

 if(isPrime) {

     prime.push(i)}

    isPrime = true

}

    return prime.length

}

 

이게 내가 개선한 코드이고, 위 블로그 역시 첫 접근도 나와 비슷하게 풀어나간 것 같다.

 

이렇게 소수에 대해 또 하나 배웁니다...