골드바흐의 추측을 알고리즘 문제에 적용하는 방법

1. 문제 1153번: 네 개의 소수 (acmicpc.net) 1153번: 네 개의 소수 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. www.acmicpc.net 임의의 자연수가 소수 4개의 합으로 분해될 수 있는지 구하는 문제 2. 풀이 어떻게 푸는지 모르겠다면.. 브루트 포스로 접근해보는게 가장 현명하다 n이 주어질때 n을 4개의 소수의 합으로 분해하고 싶다면, n보다 작은 소수들로만 분해할 수 있을 것이다 n보다 작은 소수의 리스트를 에라토스테네스의 체로 구하고 이 체에서 4중 for문으로 4개를 선택해서 더해보고 n이 되는지 검사해서 찾기만 하면 바로 break해서 탈출하고 출력해준다 from sy..

• format_list_bulleted 정수론
• · 2023. 2. 6.
• textsms

게임이론 배우기 -소수 부르기 게임-

1. 문제 25632번: 소수 부르기 게임 (acmicpc.net) 25632번: 소수 부르기 게임 용태가 부를 수 있는 소수는 $11, 13, 17$이고, 유진이가 부를 수 있는 소수는 $13, 17, 19$이다. 둘 다 최선을 다해서 플레이한다면 $13 → 17 → 11 → 19$로 진행될 수 있다. 용태가 더 이상 부를 소수가 www.acmicpc.net 2. 풀이1 두 플레이어가 주어진 범위 a,b와 c,d에서 각각 소수를 찾는다 만약 승리를 위해 최선을 다해서 플레이한다면, 어떻게 해야 할까 핵심 규칙은 이미 부른 소수는 부르지 못한다는 것이다 그러므로 상대가 가지고 있는 소수를 내가 먼저 부른다면, 상대가 가지고 있는 소수를 부르지 못하게 하면서 동시에 나는 턴을 넘기므로 매우 유리해진다 따라..

• format_list_bulleted 게임이론
• · 2023. 1. 30.
• textsms