문제

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

입력

첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

출력

첫째 줄에 총 몇 개가 있는지 출력한다.

제한

1 ≤ A ≤ B ≤ 10^14

로직

logic
에라토스테네스의 체를 활용해 풀이를 해야시간초과/메모리초과 없이 통과하는 문제
에라토스테네스의 체를 활용해서 풀이를 하면 시간을 많이 단축시킬 수 있는데, 핵심은
소수 여부를 담을 배열을 활용
소수를 구할 때 최대약수는 아무리 커도 제곱근보다 클 수 없다는 점을 활용해서 pow(n,0.5)만 구함
체에 거르듯 소수들을 걸러주고, 이 소수들을 제곱을 계속했을 경우 두 입력값 중 큰 값보다 작으면 count 변수를 증가시키고, 아니면 다음 소수로 넘어가서 count 구해기

후기

• 소수 배열을 만들 때 그냥 Math.sqrt(B)로 해줬는데 float가 되어버려서 배열을 만들어줄 때 error가 발생했다. 가장 근접한 int값으로 반올림 위해 Math.ceil함수를 써서 해결.
• 이전풀이 같은 경우에는 input을 받아올 때 const input:string|null = prompt("숫자 A B를 입력해주세요.")로 타입 단언보다는 타입 선언을 주로 써봐서 한번 타입단언을 써봤었는데..둘의 차이는 타입 단언(as 어떤타입)은 강제로 타입을 지정해줘서 일단 경고는 안뜰 거라고 예상. 타입 선언은 :string타입으로 해주면 input가 null일 수도 있다고 경고 줌.근데 string이 숫자가 아니면 결국 배열길이를 지정해줄 때 문제가 돼서 코드 수정.
  
• 구조분해를 써서 B가 소수 여부를 담을 배열의 길이에 해당된 입력값이었는데, 엉뚱한 값을 입력했을 때 에러처리가 안됐지만 split()해줬을 때 typeof 체크해줘서 number 타입아니면 -1로 지정. 배열 만들어주기 전에 -1값이면 아래와 같이 에러메세지 찍어주기
  .
  

풀이

//A,B값으로 엉뚱한 값을 줬을 때 에러처리 안됨
{
  const input = prompt("숫자 A B를 입력해주세요.") as string;
  if (!input) {
    console.log("입력값이 부적절합니다.");
  } else {
    const [A, B]: Array<number> = input.split(" ").map((v) => parseInt(v));
    const dv: number = Math.ceil(Math.sqrt(B));
    const primes: Array<boolean> = new Array(dv + 1).fill(true);
    primes[1] = false; //1은 소수가 아니다.
    for (let i = 2; i < dv + 1; i++) {
      //소수 계산
      if (primes[i]) {
        if (i * i > dv) {
          break;
        }
        for (let j = Math.pow(i, 2); j < dv + 1; j += i) {
          primes[j] = false;
        }
      }
    }

    let cnt: number = 0;
    for (let i = 1; i < primes.length; i++) {
      if (primes[i]) {
        let result = i * i;
        while (true) {
          if (result < A) {
            result *= i;
            continue;
          }
          if (result > B) {
            break;
          }
          result *= i;
          cnt += 1;
        }
      }
    }
    console.log(cnt);
  }
}
/*
test1

input
1 1000

output
25

----

test2

input
1 10

output
3

----

test3

input
5324 894739

output
183

*/

• 입력값 에러처리

{
  const input :null | string= prompt("숫자 A B를 입력해주세요.");
  const invalid_input=()=>{console.log("입력값이 부적절합니다.")};
  if (!input) {
    invalid_input();
  } else {
        const [A, B]: Array<number> = input.split(" ").map((v) => typeof v==="number"? parseInt(v): -1);
        if(A || B){
            invalid_input();
        } else{
           const dv: number = Math.ceil(Math.sqrt(B));

            const primes: Array<boolean> = new Array(dv + 1).fill(true);
            primes[1] = false; //1은 소수가 아니다.
            for (let i = 2; i < dv + 1; i++) {
            //소수 계산
            if (primes[i]) {
                if (i * i > dv) {
                break;
                }
                for (let j = Math.pow(i, 2); j < dv + 1; j += i) {
                primes[j] = false;
                }
            }
            }

            let cnt: number = 0;
            for (let i = 1; i < primes.length; i++) {
            if (primes[i]) {
                let result = i * i;
                while (true) {
                if (result < A) {
                    result *= i;
                    continue;
                }
                if (result > B) {
                    break;
                }
                result *= i;
                cnt += 1;
                }
            }
            }
            console.log(cnt); 
        }
        
    }
    
}