-
[프로그래머스] 소수 찾기Algorithm 2021. 1. 18. 22:03
programmers.co.kr/learn/courses/30/lessons/12921
코딩테스트 연습 - 소수 찾기
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상
programmers.co.kr
더보기문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)
제한 조건
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result 10 4 5 3 풀이
function solution(n) { // 소수는 1과 자기 자신으로만 나누어지는 숫자 let count = 0; for (let i = 2; i <= n; i++) { let check = true; for(let j = 2; j < i; j++) { if(i % j === 0) { check = false; } } if(check) count++; } return count; }
실행 결과
정확성: 9개 통과, 10~12 실패(시간 초과)
효율성: 1~4 실패(시간 초과)
시간복잡도 O(n)
에라토스테네스의 체
에라토스테네스의 체: 소수를 판별하는 알고리즘
function solution(n) { let answer = 0; let arr = []; for (let i = 2; i <= n; i++) { arr[i] = i; } for (let i = 2; i <= n; i++) { if (arr[i] === 0) continue; for (let j = i + i; j <= n; j += i) { arr[j] = 0; } } for (let i = 2; i <= n; i++) { if (arr[i] !== 0) answer++; } return answer; }
function solution(n) { let arr = [] for(let i = 1; i <= n; i++) { arr.push(i) } for(let i = 1; i * i < n; i++) { if(arr[i]) { let num = arr[i] for(let j = num * num; j <=n; j += num) { arr[j-1] = 0; } } } let answer = arr.filter((number) => number) answer.shift() return answer.length; }
'Algorithm' 카테고리의 다른 글
[프로그래머스] 두 개 뽑아서 더하기 (0) 2021.01.20 [프로그래머스] K번째수 (0) 2021.01.18 [프로그래머스] 약수의 합 (0) 2021.01.18 [Codewars] Valid Braces (0) 2020.11.16 [Codewars] Format a string of names like 'Bart, Lisa & Maggie' (0) 2020.11.08