[C++] 백준 1016 : 제곱 ㄴㄴ 수

#include <iostream>
#include <cmath>

using namespace std;

long long num[1000001] = {0}; // 최대 1,000,000개 수 체크 - 양수면 제곱ㅇㅇ수
long long minN, maxN;

int main() {
  cin >> minN >> maxN;
  int cnt = 0;

  // 제곱 구할 수 반복문
  for(long long i = 2; i <= sqrt(maxN); i++){
    // 제곱수의 배수 시작 찾기
    long long n = minN / (i * i); // 제곱수 몫 찾기, () 주의하기 minN/i * i 라고 쓰면 안됨
    
    // minN이 제곱수로 나누어지지 않는 경우
    if(minN % (i * i)){
      n += 1; // 다음 몫부터 계산 시작
    }
    // minN이 제곱수로 나누어지는 경우에는 그대로 그 몫부터 계산해주면 된다.

    // maxN까지 제곱수 에라토스테네스의 체
    while(n * i * i <= maxN){
      num[n * i * i - minN] = 1; // 제곱ㅇㅇ수 체크
      n++; // 다음 제곱 수 찾기
    }
  }

  for(int i = 0; i <= maxN - minN; i++){
    if(num[i] == 0){
      cnt++;
    }
  }

  cout << cnt;

  return 0;
}

segmentation fault 에러 무진장 많이 나서 왜 골드 1인지 알 수 있었던 문제...

인터넷 좀 열심히 찾아봤다. 에라토스테네스의 체를 써야 효율적이라는 사실은 알았는데 어떻게해야 1조나 되는 수의 제곱수를 바로 알아낼 수 있을지에 대해서 생각이 떠오르지 않았는데

그냥 나눠서 몫을 이용해서 곱해주면 된다는 사실을 잊었다... 생각? 그거 어떻게 하는건데

정말 모든 문제는 조건문과 반복문을 사용하면 풀 수 있다는 말이 맞는 것 같다.