[프로그래머스] 코딩테스트 연습 - 소수 찾기 (javascript)

문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

약수에 삘받아서 소수문제도 도전.

생각해본 풀이법

1. for문 두개 돌릴 예정.
   1.1 2부터 n까지 i를 키워가며 약수의 개수를 구하기 위해 반복하는 for문
   1.2 그 안에 또 1부터 i까지 돌아가는 for문 만들고 그 안에 i의 약수를 담아줄 temporary 선언
   1.3 if문 돌려서 약수들 temporary에 담고 length가 2인 i만 arr.push
2. 빈 배열을 만들어서 소수 집어넣고 return arr.length하면 될듯

function solution(n) {
    let arr = [];
    for (let i = 2; i <= n; i++){
        let temporary = [];
        for (let j= 1; j <= i;j++){
            if(i % j === 0){
                temporary.push(j)
            }
        }
        if (temporary.length === 2) {
            arr.push(i)
        }
    }return arr.length
}

돌려보니 돌아가기는 하는데.. 더 좋은 방법이 있을텐데...ㅜㅜ
일단 제출 후 다른 답안 공부해야지
라고 생각했는데 제출해보니 시간초과라니..

이런건 또 처음본다....

최적화 고민하다가 얻게 된 힌트

이걸 한번 구현해볼까 한다.

생각해본 풀이법

1. 일단 arr 안에 2부터 n까지 배열에 담아준다. (for문 사용)
2. 2부터 시작해서 i의 배수인 숫자들은 0으로 바꿔준다(for 문 안에 있는 조건 사용)
3. filter 사용해서 0이 아닌 숫자들만 뽑아서 length 구하기

function solution(n) {
    let arr =[]
    for (let i = 2; i <= n; i++) { 
        arr[i] = i 
    } 
    for (let i = 2; i <= n; i++) { 
        for (let j = i + i; j <= n; j += i) { 
            arr[j] = 0 
        } 
    } 
    return arr.filter((item) => item !== 0).length 
}

후 힘들었다....ㅜㅜ

10점 완!

Set 사용해서 푼 방법

function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<Math.sqrt(n); j++){
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){    
                s.delete(k);
             }
        }
    }
    return s.size;
}

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 광기로 푼 답안
(수박수박수박 2탄인디)

function solution(n) {
    var answer = 0;

    for(e=2;e<=n;e++){
        if(e&1&&e%3&&e%5&&e%7 &&e%11&&e%13&&e%17&&e%19&&e%23&&e%29&&e%31&&e%37&&e%41&&e%43&&e%47&&e%53&&e%59&&e%61&&e%67&&e%71&&e%73&&e%79&&e%83&&e%89&&e%97&&e%101&&e%103&&e%107&&e%109&&e%113&&e%127&&e%131&&e%137&&e%139&&e%149&&e%151&&e%157&&e%163&&e%167&&e%173&&e%179&&e%181&&e%191&&e%193&&e%197&&e%199&&e%211&&e%223&&e%227&&e%229&&e%233&&e%239&&e%241&&e%251&&e%257&&e%263&&e%269&&e%271&&e%277&&e%281&&e%283&&e%293&&e%307&&e%311&&e%313&&e%317&&e%331&&e%337&&e%347&&e%349&&e%353&&e%359&&e%367&&e%373&&e%379&&e%383&&e%389&&e%397&&e%401&&e%409&&e%419&&e%421&&e%431&&e%433&&e%439&&e%443&&e%449&&e%457&&e%461&&e%463&&e%467&&e%479&&e%487&&e%491&&e%499&&e%503&&e%509&&e%521&&e%523&&e%541&&e%547&&e%557&&e%563&&e%569&&e%571&&e%577&&e%587&&e%593&&e%599&&e%601&&e%607&&e%613&&e%617&&e%619&&e%631&&e%641&&e%643&&e%647&&e%653&&e%659&&e%661&&e%673&&e%677&&e%683&&e%691&&e%701&&e%709&&e%719&&e%727&&e%733&&e%739&&e%743&&e%751&&e%757&&e%761&&e%769&&e%773&&e%787&&e%797&&e%809&&e%811&&e%821&&e%823&&e%827&&e%829&&e%839&&e%853&&e%857&&e%859&&e%863&&e%877&&e%881&&e%883&&e%887&&e%907&&e%911&&e%919&&e%929&&e%937&&e%941&&e%947&&e%953&&e%967&&e%971&&e%977&&e%983&&e%991&&e%997)
        answer++;

    return n==2 ? 1 : n==171 ? 39 : n==458 ? 88 : n==633 ? 115 : n==938 ? 159 : answer+168;
}

length 말고 count 로 세는 방법

function numberOfPrime(n) {
  if(n == 2) return 1

  var count = 0;
  for(var i=2; i <= n; i++){
    var a = 2; // 사이클이 시작할때마다 a = 2 로 리셋
      while(a < i) { //이렇게하면 자신의 숫자로 나누어질 일은 없다.
        if(i % a != 0) { // 그리고 나누어지지않으면 계속, 나누어지면 카운트하고 끝
             a++;
        } else {
            count++
          break;
        }
      }
    }
  return n - count -1;
  // 카운트된 것은 소수가 아닌것들이고, -1을 더 해주는 이유는 1의 경우때문이다.
}



// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log( numberOfPrime(10) )

방법이 엄청 다양하다...!
공부가 훨씬 더 많이 필요하다고 느끼게 해준 문제였음....