Erathosthenes 2

BAEKJOON 1017 - 소수 쌍

문제: https://www.acmicpc.net/problem/1017 우선 에라토스테네스의 체 방법으로 2000 까지 소수를 구해놓고 앞의 1014번 문제에서 사용한적이 있던 network flow (Ford Fulkerson algorithm) 방법으로 bipartite matching 문제를 푸는 방법을 이용하여 푼 문제입니다.처음에 이분 매칭(bipartite matching) 의 조건을 구성하는 것이 생각하기 어려운 부분일 수 있는데 주어진 숫자를 짝수와 홀수로 나눠 이분 그래프를 만드는 것이 중요합니다. 짝수와 짝수 또는 홀수와 홀수로는 무조건 짝수값이 나오기 때문에 소수가 절대 될 수 없고 이 점 때문에 이분 그래프가 성립이 될 수 있는거죠.그리고 첫 번째 주어진 값과 연결될 수 있는 값을..

BAEKJOON 1016 - 제곱 ㄴㄴ 수

문제: https://www.acmicpc.net/problem/1016 시간 복잡도를 줄이기위해 에라토스테네스의 체 방법을 사용해야했고, 공간 복잡도를 줄이기 위해 bit mask 방법과 주어진 최소값부터 에라토스테네스의 체를 적용하는 방법을 사용해 풀었습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #include using namespace std;typedef long long ll; const ll MAX_N = 1000003;unsigned char sieve[(..