https://school.programmers.co.kr/learn/courses/30/lessons/12921
문제 설명
부터 입력받은 숫자 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) {
var answer = 0;
let chk=0;
for(let i = 2;i<=n;i++){
chk=1;
for(let j=2;j<=Math.sqrt(i);j++){
if(i%j == 0){
chk=0;
}
}
if(chk){
answer++;
}
}
return answer;
}효율적으로 해결할 방법이 안 떠올라서 단순하게 2중 for문으로 했다. 당연히 효율성 테스트 전부 실패했다.
코드 - 효율성 테스트 실패 2
function solution(n) {
var answer = 0;
let num = Array(n).fill(0);
num = num.map((x, idx) => {return idx+1});
num = num.filter(x => {
for(let i=2;i<=Math.sqrt(x);i++){
if(x%i == 0){
return false;
}
}
return true;
})
return num.length-1;
}1부터 n까지 배열에 집어넣고 filter를 써봤는데 효율성 테스트 하나만 통과했다.
코드 - 효율성 테스트 실패 3
function solution(n) {
var answer = 0;
let num = [2, 3, 5, 7, 11];
if(n <= 11){
return num.filter(x => x<=n).length;
}
let chk = 0;
for(let i = 12;i<=n;i++){
chk = 1;
for(let j of num){
if(i%j == 0){
chk=0;
}
}
if(chk){
num.push(i);
}
}
return num.length;
}소수 배열 하나 만들어서 소수 배열에 있는 수로 나누어보고자 했는데 효율성 실패. 정확성 테스트 10, 11, 12도 시간초과로 실패
코드 - 효율성 테스트 실패 4
function solution(n) {
var answer = 0;
let num = Array(n-1).fill(1);
num = num.map((x, idx) => idx+2);
for(let i=2;i<=Math.sqrt(n);i++){
if(num.includes(i)){
num = num.filter(x => x%i || x == i);
}
}
return num.length;
}에라토스테네스의 체를 참고해서 2부터 n까지 숫자 만들고 2부터 시작해서 배수인 애들은 filter로 걸렀는데 효율성 테스트 4개 다 실패했다.
코드 - 효율성 테스트 실패 5
function solution(n) {
let num = [2, 3, 5, 7, 11];
if(n <= 11){
return num.filter(x => x<=n).length;
}
let chk = 0;
for(let i = 12;i<=n;i++){
chk = 1;
for(let j=0;num[j]<=Math.sqrt(i)&&j<num.length;j++){
if(i%num[j] == 0){
chk=0;
}
}
if(chk){
num.push(i);
}
}
return num.length;
}에라토스테네스의 체 만들고 숫자의 제곱근만큼만 비교하는 과정도 했는데 테스트 실패했다.
코드 - 성공
function solution(n) {
let num = Array(n+1).fill(0);
num = num.map((x, idx) => {return idx});
num[0] = 0;
num[1] = 0;
for(let i = 0;i<num.length;i++){
if(!num[i]) continue;
for(let j = num[i]*2;j<num.length;j+=num[i]){
num[j] = 0;
}
}
return num.filter(x => x).length;
}질문하기를 참고해서 n까지의 숫자가 담긴 배열을 만들고 배열을 돌면서 소수의 2배수부터 배수는 전부 0으로 채워넣었다.
방법은 filter나 map이랑 비슷한거 같은데 for문으로 idx 통제하는게(map이나 filter는 배열의 모든 요소 탐색하는 느낌이라면 for로 idx 통제하면 예를들어 7배수면 14, 21, 28만 접근하게 할 수 있음) 상대적으로 더 빠른가보다.
map, filter와 for문의 속도를 비교한 자료가 있는지 찾아봐야할듯
https://blog.naver.com/PostView.nhn?blogId=thdwlsgus0&logNo=222269338961&parentCategoryNo=&categoryNo=26&viewDate=&isShowPopularPosts=true&from=search
여기 글을 참고하니까 for문이 다른 배열 메소드보다 빠르다고 나왔다. 편하다고 메소드 쓰지 않고 for문으로 하는 연습을 해야겠다.
