목록에라토스테네스의 체 (2)
전자공학 및 알고리즘
백준 2960 - 에라토스테네스의 체(C++)
문제 링크입니다. https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 에라토스테네스의 체를 사용하는 문제입니다. 에라토스테네스의 체 기본 원리를 이용해 지워지는 K번째 수를 구하는 문제입니다. 여기서는 소수도 지워야함으로 이를 고려해주기만 하면 쉽게 풀 수 있습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; int N, K; int check[1001]; ..
백준 1963 - 소수 경로(C++)
문제 링크입니다 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 에라토스테네스의 체 + BFS를 이용하는 문제였습니다! 문제 접근 방법 1. 에라토스테네스의 체를 이용해 1000~9999까지의 소수를 구한다 2. 소수 한 쌍을 입력받은 뒤, 소수 경로를 구하는 BFS에 저장한다. 3. answer의 값에 따라 출력한다. 문제 접근 방법 - 1번 void find_prime_number() { for (int i = 2; i = 1000 && check[..