대엉코딩

www.acmicpc.net/problem/1837

1. 풀이방법

- 첫번째는 소수 판별과 두번째는 longlong 범위를 넘어가는 big integer에 대한 mod연산 구현

- 이 두가지를 구현하는 문제 인데 첫번째는 에라토스테네스의 채를 이용하여 소수 set을 만들었고 (k의최대값까지)

- string으로 큰수를 받아서 (10^100 이므로) c++에서 제공하는 정수를 담는 자료형으로는 어림도 없으므로

- 그 문자열로 받은 큰 수를 int로 나누어보는 함수를 구현하였다 (나누는 수는 k보다 작으므로 int 가능)

2. 주의사항

- 제 구현에서는 소수 set을 만드는 부분과 나누어지는지 확인하는 부분이 나누어져있지만

- 짜고 나서 보니 에라토스테네스의 체를 이용하여 구해가면서 그때그때 판별을 하면 연산의 수를 줄일 수 있을

- 것 같습니다.

3. 나의코드

#include<bits/stdc++.h>
using namespace std;
const int maxk= 1e6+1;

bool isitprime[maxk]; //false 이면 소수
string ps;
int k;
int resulti = 0;

void makeprimeset() { //소수 판별
	isitprime[0] = true; isitprime[1] = true;
	for (int i = 2; i <= k; i++) {
		if (isitprime[i] == false) { //소수이면
			int index = i;
			int tmp = 2;
			while (index * tmp <= k) { //배수는 모두 소수가 아님
				isitprime[index * tmp] = true;
				tmp++;
			}
		}
	}
}
bool bigintdivide(int p) {
	int tmpsum = 0;
	for (int i = 0; i < ps.length(); i++) {
		tmpsum = (tmpsum * 10 + (ps[i] - '0'))%p; //앞자리수 부터
	}
	if (tmpsum == 0) return true;
	else return false;
}

bool isunderk() {
	for (int i = 2; i <k; i++) {
		if (isitprime[i] == false) {
			if (bigintdivide(i)) {
				resulti = i; return false;
			}
		}
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> ps >> k;

	makeprimeset(); //에라토스테네스의 채
	if (isunderk()) cout << "GOOD" << "\n";
	else cout << "BAD" << " " << resulti << "\n";


	return 0;
} 

www.acmicpc.net/problem/2609

1. 풀이방법

 - 유클리드 호제법을 이용한 최대공약수 , 최대공배수 구하는 문제입니다.

2. 나의코드

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int GCD(int n1, int n2) {
	if (n2==0) return n1;
	return GCD(n2, n1%n2);
}
int LCM(int n1, int n2) {
	return n1 * n2 / (GCD(n1, n2));
}


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

	int num1, num2;
	cin >> num1 >> num2;
	cout << GCD(num1, num2) <<"\n"<<LCM(num1,num2)<<"\n";

	return 0;
}