소수 찾기

내 코드

function solution(n) {
    var answer = 0;
    
    let ary = []
    
    for(let i=2; i<=n; i++){
       for(let j=2; j<i; j++){
           
           if(i % j === 0){
               ary.push(i)
               break;
           }
       }
    }
    
    return answer = n - ary.length-1
}

2중 for문으로 자기자신까지 돌면서 나눈 값이 0이면 for문을 멈추고 그 값을 ary에 저장을 한다.

원래 n 값에 0으로 나뉘어서 소수로 가 아닌갯수 - 1 을 빼주면 됬다.

 

-1을 해준 이유는 1은 소수가 아니기 때문에 보너스처럼 1개를 더 빼준 로직..

 

하지만 시간초과로 실패가 됫다.

흠...

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

이게 초기 범위 값인데 아마 여기서 너무 많은 숫자를 2중 for문으로 돌리다보니 O(n^2)라서 뻗어버린게 아닐까?

알고리즘과 빅오표기법, 성능은 잘은 모르지만 일단 실패니 개선해야했음

 

에라토스테네스체)

구글링 해보니 에라토스테네스체 라는 수학적 기법이 나와있음

한마디로 100까지 숫자 중 소수를 구할 때 루트 100을 한 값 10까지의 배수만 제거하면 100까지의 소수가 구해진다

 

음 그러니까 아무리 값이 커져도 자기 숫자의 루트 값만큼 제거하면 됨,

 

답지)

function solution(n) {
    var answer = 0;

    for(let i=1; i<=n; i++){
        if(isPrime(i)){
            answer++
        }
    }
    
    return answer;
}

function isPrime(num){
    
    if(num === 1){
        return false
    }
    
    if(num === 2){
        return true
    }
    
    for(let i=2; i<=Math.floor(Math.sqrt(num)); i++){
        if(num%i === 0){
            return false
        }
    }
    return true
}

 

1. isPrime 함수로 n 의 값을 받아서 1 은 소수가 아니므로 false 2는 소수이므로 true 를 먼저 선언해줌

2. for 문으로 매개변수 num의 에라토스테네스체의 기법으로 루트(*제곱근) 만큼의 소수만 제거해준다.

 

ex)

num = 5 일때,

5의 제곱근은 3이고

1, 2, 3, 4, 5 중 1, 2, 3 의 배수만 제거하면 1, 2, 3, 4(2의 배수)가 제거되고 5만 남게 된다.
자기 자신으로밖에 안나눠지기 때문에 5는 소수가 된다.

num = 4 일때

4의 제곱근은 2고

1,2,3,4 중 1, 2 의 배수만 제거하면 1, 2, ,4 가 제거 되지만 3이 남기 때문에 소수가 아니다.

이런식으로 계산해주면 된다.