백준 #1016 제곱 ㄴㄴ수

이번 문제는 1을 제외한 제곱수로 나누어 떨어지는 수를 구하는 것입니다.  에라토스테네스 체의 확장판이라고 생각하시면 될 것 같네요.

그리고 숫자의 범위는 작지만 숫자 자체가 꽤 커서 소수를 꽤 많이 구해야 합니다.  어떤 수 \(n\)이 소수인지는 \(O(\sqrt{n})\)의 복잡도로 판단할 수 있어서, 숫자가 \(10^{12}\) 오더이긴 하지만 제곱수이기 때문에 실제 구해야할 소수는 \(10^6\) 오더입니다.  계산량으로 보면 제한시간의 절반 이하로 가능합니다.  그런데 정답비율은 18%로 아주 낮습니다.

 

문제는 아래의 링크에 있습니다.

https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

주어진 범위가 (min, max)로 주어지기 때문에 에라토스테네스의 체를 구성하려면 offset 개념을 두어야 합니다.  당연히 min이 offset 수치가 되겠죠.  전 소수 \(p\)를 구한 후에 \(p^2\)으로 min 값을 나눈 나머지로 offset을 썼습니다.  2에 대해서는 미리 처리를 하면, 소수 검사를 할 때 홀수만을 사용할 수 있습니다.

 

아래는 제가 작성한 소스입니다.  소스는 참고용으로만 봐주세요.

//----------------------------------------------------------------------------------------
//  baekjoon #1016 - Square NO-No Number
//    - by Aubrey Choi
//    - created at 2019-06-14
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <math.h>

static char check[1000001];
void mark(long long p, long long r, int n)
{
  for(long long i = (p - r)%p; i < n; i += p) check[i] = 1;
}
int main()
{
  long long min, max, r;
  int k, n, c = 0;
  scanf("%lld%lld", &min, &max);
  k = (int)sqrt(max);
  r = min % 4;
  n = (int)(max - min + 1);
  mark(4, r, n);
  for(long long p = 3; p <= k; p += 2)
  {
    r = min % (p*p);
    mark(p*p, r, n);
  }
  for(int i = 0; i < n; i++) if(check[i] == 0) c++;
  printf("%d\n", c);
}