[백준 1456] 거의 소수

www.acmicpc.net/problem/1456

1456번: 거의 소수

에라토스테네스의 체를 사용하면 되지만 소수 제곱을 확인하는 과정에서 long long으로 선언해도 오버플로우가 발생한다.

예를 들어 i =10^7이고, tmp = 10^14라면

tmp * i = 10^21을 확인할 때 계산 자체가 오버플로우기 때문이다.

따라서!

if( i * tmp <=m) 대신 if(i <= m/tmp)를 추가한다.

 

소수를 따로 저장하지 않고 계산하는 경우

#include <stdio.h>
#define ll long long
using namespace std;

ll n, m;
ll arr[10000011];
int main(void)
{
  scanf("%lld %lld", &n, &m);

  arr[1] = 1;
  for (ll i = 2; i * i <= m; i++)
  {
    if (arr[i])
      continue;
    for (ll j = 2; j * j * i * i <= m; j++)
    {
      arr[j * i] = 1;
    }
  }
  ll res = 0;
  for (ll i = 2; i <= m / i; i++)
  {
    if (arr[i])
      continue;

    ll tmp = i;
    while (tmp <= m / i)
    {
      if (tmp * i >= n)
      {
        res++;
        //printf("%lld ", tmp);
      }

      tmp *= i;
    }
  }

  printf("%lld\n", res);
  return 0;
}

 

소수를 따로 저장한 경우

#include <stdio.h>
#include <vector>
#define ll long long
using namespace std;

ll n, m;
ll arr[10000011];
vector<ll> v;
int main(void)
{
  scanf("%lld %lld", &n, &m);

  arr[1] = 1;
  for (ll i = 2; i * i <= m; i++)
  {
    if (arr[i])
      continue;
    for (ll j = i << 1; j * j <= m; j += i)
    {
      arr[j] = 1;
    }
    v.push_back(i);
  }

  ll res = 0;
  int sze = v.size();
  for (int i = 0; i < sze; i++)
  {
    ll tmp = v[i];

    while (v[i] <= m / tmp)
    {
      if (tmp * v[i] >= n)
      {
        res++;
        //printf("%lld ", tmp);
      }

      tmp *= v[i];
    }
  }

  printf("%lld\n", res);
  return 0;
}