// trial 1

// 효율성 시간 초과
function solution2(n) {
  var answer = 0;

  if (n > 2) {
    let i = 3;

    while (i <= n) {
      isPrime(i) && answer++;
      i++;
    }

    return ++answer; //n이 2일 때
  }
  return 1;
}

function isPrime(n) {
  let i = 2;
  while (i <= Math.sqrt(n)) {
    if (n % i === 0) return false;

    i++;
  }
  return true;
}
/* 
  isPrime
    2 ~ sqrt값까지 약수인지 판별
  
  solution2
    입력값이 2부터 주어지므로, 2일 경우 1을 return하고
    n이 3일 때부터는, 3부터 n까지 소수인지 판별해 소수일 경우, answer를 증가시킴.
    이 경우, n까지의 정수에 대해 매번 isPrime을 실행하므로 효율성이 꽝.
  */

//trial 2
//효율성 시간 초과

function solution2(n) {
  if (n === 2) {
    return 1;
  }
  if (n === 3) {
    return 2;
  }
  if (n <= 5) {
    return 3;
  }
  if (n <= 7) {
    return 4;
  }

  let answer = 4;
  for (let i = 11; i <= n; i += 2) {
    if (i % 3 == 0) continue;
    if (i % 5 == 0) continue;
    if (i % 7 == 0) continue;
    if (isPrime(i)) {
      answer += 1;
    }
  }

  return answer;
}

/*
    2,3,5,7까지의 n에 대해 구해진 결과를 리턴하고,
    11부터 홀수에 대해서만 소수를 판별해 소수 판별 시행을 줄여봄.
    3, 5, 7의 배수일 경우 소수 판별 없이 다음 정수로 넘어감.
  */
//trial 3

// 효율성 통과

function solution2(n) {
  let answer = 0;
  const primeArr = Array(n + 1).fill(1);
  //인덱스와 정수를 일치시키기 위해 n+1 array 생성

  primeArr[0] = 0;
  primeArr[1] = 0;
  //prime이 아닌 0,1은 0으로 체크

  fillPrimeArr(2, primeArr);
  fillPrimeArr(3, primeArr);
  fillPrimeArr(5, primeArr);
  fillPrimeArr(7, primeArr);

  for (let i = 11; i <= Math.sqrt(n); i += 2) {
    //11부터 홀수가 prime일 경우, fillPrime 시행
    if (i % 3 === 0) continue;
    if (i % 5 === 0) continue;
    if (i % 7 === 0) continue;
    isPrime(i) && fillPrimeArr(i, primeArr);
  }

  for (let tf of primeArr) {
    tf && answer++;
  }

  return answer;
}

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

function fillPrimeArr(prime, arr) {
  for (let i = prime * 2; i < arr.length; i += prime) {
    arr[i] = 0;
    //prime은 1로 남기고 prime의 배수는 모두 0으로 체크
  }
}

function othersSolution2(n) {
  const s = new Set();
  for (let i = 1; i <= n; i += 2) {
    s.add(i);
  }
  s.delete(1);
  s.add(2);
  // 2,3,5,7,9,11,13,... 2와 n이하의 홀수

  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;
}
// trial 3와 반대 방식으로 푼 풀이
// set을 사용 지니어스..
// 먼저 채우고
// set에 포함되었을 경우, delete

function solution2(n) {
  let s = [...Array(n).keys()]; // [0,1,2,3,4,5,...,n-1,n]
  // console.log(s);
  s[0] = 0;
  for (let i = 2; i <= parseInt(n ** 0.5) + 1; i++) {
    // console.log(i);

    for (let j = 2; j <= (n - i) / i + 1; j++) {
      // j <= n/i
      s[i * j - 1] = 0;
    }
  }
  return s.filter((x) => Boolean(x)).length;
}