[틀림] 백준 1456 거의소수 // 대소비교 최적화방법, 소수판별

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

* 풀이1

• 체 알고리즘 => 소수들 벡터에 저장 ( 루트b까지만 보면됨 )
  • ex) 25까지의 거의소수를구해야함
  • 5까지만 소수를 구하면됨. 구해야됨.
  • 10^14 -> long도 초과, 10^7 -> 1천만 -> ok 
    • 5를넘어가면 (6부터는 6^2 = 36 ...) 거의소수가 될수없음.

• 1. 소수에대해
• 2. 소수들을 제곱해가면서 a이상, b이하인지 체크

for(auto i : v) {
   int cnt=0;
   for(ll j=i*i;j<=b;j=j*i) {
      if(j>=a) cnt++;
   }
   ret+=cnt;
}

• 문제 : j를 계속 곱하기때문에 overflow 발생

 

* 풀이2

• 이항정리를 이용한 대소비교
• 이렇게하면 77777^10을 계산해야될것을, 77777^9으로 개선할수있음.

for(auto i : v) {
   int cnt=0;
   ll tmp = i; // 777777(소수)
   while((double)i <= (double)b / (double)tmp) {
      if( (double)i >= (double)a/(double)tmp) {
         cnt++;
      }
      tmp = tmp * i;
   }
   ret+=cnt;
}

 

* 전체코드

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

ll a,b,ret;
int sosu[10000000+1];
vector<ll> v;

void make() {
   fill(sosu,sosu+10000000+1,1); //모두 소수라고 가정
   sosu[1]=0;// 1은 소수아님
   for(ll i=2;i*i<=b;++i) {
      if(!sosu[i]) continue;
      for(ll j=2*i;j*j<=b;j+=i) { //소수 i의 배수들은 소수가아님, 시작 : 2*i부터!!
         sosu[j]=0; // 이문제특징 : 소수를 루트b까지만 구하면됨!!!, 다구하면 10^14 -> 터짐
      }
   }

   for(ll i=2;i*i<=b;++i) {
      if(sosu[i]) {
         v.push_back(i);
      }
   }
   
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   cin>>a>>b;
   make();
   for(auto i : v) {
      int cnt=0;
      ll tmp = i; // 777777(소수)
      while((double)i <= (double)b / (double)tmp) {
         if( (double)i >= (double)a/(double)tmp) {
            cnt++;
         }
         tmp = tmp * i;
      }
      ret+=cnt;
   }

   cout<<ret;
   
   return 0;
}