백준 1837번 암호제작

< 백준 1837번 암호제작 - 마포 코딩박 >

사용한 알고리즘: 에라토스테네스의 체

 두 소수 p,q 의 곱으로 이루어진 수 P와 기준이 되는 수 K 가 주어집니다.
 p,q 둘 중 하나라도 K 미만이면 BAD 이고, 아니면 GOOD 입니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~16)
 구현의 편의를 위해 두 소수의 곱 P를 string으로 받았습니다.
 P가 임의의 소수 num 으로 나누어 떨어지는지 확인하는 함수를 만듭니다.

(2) (코드 22~33)
 에라토스테네스의 체를 이용하여 2이상 K미만의 소수를 차례로 봅니다. 모든 해당 소수 i 에 대해 P 를 나눌 수 있는지 과정 (1) 에 만든 함수로 확인합니다.
 모든 소수가 나눌 수 없다면 GOOD 이고, 하나라도 나눌 수 있으면 BAD 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	const int MOD = 1e6;
	bool visited[MOD];
	int K;
	string P;
	// P가 소수 num으로 나누어 떨어지는지 본다.
	bool check(int num){
	int sum = 0;
	// 주어진 수 P 를 각 자리수별로(큰 자리수부터) 나누어 본다
	for(int i=0; P[i];i++)
	sum = (sum*10+(P[i]-'0'))%num;
	if(sum==0) return true;
	return false;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> P >> K;
	bool good = true;
	int ans = 0;
	// P가 K 이하의 소수로 나누어 떨어지는지 본다.
	for(int i=2; i<K; ++i){
	if(visited[i]) continue;
	// 소수 i 로 P가 나누어 떨어지는지 여부 체크
	if(check(i)){
	good = false;
	ans = i;
	break;
	}
	// 소수 아닌애들 지움. 에라토스테네스의 체
	for(int j=2*i; j<K; j+=i) visited[j] = true;
	}
	if(good) cout << "GOOD" << '\n';
	else cout << "BAD " << ans << '\n';
	return 0;
	}

view raw BOJ 1837.cpp hosted with ❤ by GitHub