프로그래밍

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

[난이도] Gold4
[유형] 에라토스테네스의 체

[풀이]
구해야하는 값 ret이 1~N 모든 수로 나누어 떨어지려면
ret을 소인수 분해 해서 a^k1 * b^k2 * c^k3... 꼴이 됐을 때,
a,b,c...인 어떤 소수 p는 1~N 숫자 중 p를 가장 많이 가지고 있는 숫자가 가지고 있는 만큼
가지고 있어야 ret을 1~N의 모든 수를 나누어 봤을 때, p가 부족해서 나누지 못하는 경우가 생기지 않습니다.

그러므로 전체 풀이는 아래와 같습니다.

1) 에라토스테네스의 체를 이용해 N보다 작은 모든 소수를 구해서 vector에 미리 저장,
2) 각 소수 p의 거듭제급 p^k 중 N보다 작으면 가장 큰 수를 구해서 ret에 곱해줌

연산 중 int 범위를 넘어갈 수 있으므로 long long을 적절히 사용해줍니다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int N;
int mod=987654321;
bool prime[1000001];
int main(){
    scanf("%d",&N);
    for(int i=2;i<=N;i++){
        for(int j=i*2;j<=N;j+=i){
            prime[j]=1;
        }
    }
    vector<int> primes;
    for(int i=2;i<=N;i++){
        if(!prime[i]) primes.push_back(i);
    }
    ll ret=1;
    for(auto p : primes){
        if(p>N) break;
        ll k = p; 
        while(k*p<=N) k*=p;
        ret=(ret*k)%mod;
    }
    printf("%lld",ret);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1630.cpp

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

[난이도] Gold5
[유형] 에라토스테네스의 체

[풀이]
N의 최댓값이 100만보다 넉넉하게 큰 수인 500만까지 에라토스테네스의 체를 이용해 어느것이 소수인지
배열에 체크해준다.
그 뒤 N보다 큰 소수중에 가장 작은 팰린드롬인 수를 찾으면 시간내에 해결이 가능하다.

#include <cstdio>
#include <string>
using namespace std;
int N;
const int mxN=5e6;
bool np[mxN];
bool check(int n){
    string s = to_string(n);
    int sz = s.size();
    for(int i=0;i<sz/2;i++){
        if(s[i]!=s[sz-1-i]) return 0;
    }
    return 1;
}
int main(){
   scanf("%d",&N);
   np[1]=1;
   for(int i=2;i<mxN;i++){
       if(np[i]) continue;
       for(int j=i+i;j<mxN;j+=i) np[j]=1;
   }
   for(int i=2;i<mxN;i++){
       if(i>=N && !np[i] && check(i)){
           printf("%d",i);
           return 0;
       }
   }
} 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1747.cpp