소수 찾기 ★☆☆☆☆

코딩테스트 연습 - 소수 찾기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

소수의 개수를 찾는 문제다

1. 이중 포문으로 풀어준다. 겉의 포문은 구하려는 숫자(n)이고 안쪽 포문은 소수인지 검사하는 숫자(i)이다

2. n의 끝까지 검사하면 시간초과가 되기 때문에 그 절반인 2를 나누 숫자까지 i를 증가시켰다.

3. 하지만 그것도 시간초과가 떴다. 검색한 결과 따라서 n의 루트만큼 돌게 시켰다.

 

function solution(n) {
    let answer = 0;
    
    if(n == 2) return 1
    else{
        answer++
        for(let couldBPrmNum = 3; couldBPrmNum <= n; couldBPrmNum++){
            let isPrime = true
            for(let i = 2; i <= Math.sqrt(couldBPrmNum);i++){
                if(couldBPrmNum % i === 0){
                    isPrime = false
                    break
                }
            }
            if(isPrime) answer++
        }
    }
    
    return answer;
}