에라토스테네스의 체4 [백준 29728] 실버와 소수는 둘다 S로 시작한다 (C++) https://www.acmicpc.net/problem/29728문제브실이는 실버 난이도의 소수 관련 문제를 풀던 도중, "실버"와 "소수"가 동일하게 S로 시작한다는 것을 깨달았다.물론 소수는 한글로 적었을 때의 발음만 S로 시작하지, 영어로는 prime이라 틀린 말이지만 브실이는 새로운 문제를 만들 생각에 들떠 세세한 것은 신경 쓰지 않기로 했다. 브실이가 구상한 문제는 다음과 같다.먼저 빈 문자열 A를 준비한다. 그러면 브실이가 정수 N을 불러줄 것이다. 첫 번째 차례부터 N번째 차례까지 다음 작업을 진행한다.현재 차례가 소수 번째가 아닌 경우, A의 끝에 알파벳 B를 추가한다.현재 차례가 소수 번째인 경우는 조금 특별하다. 만약 A의 마지막 문자가 B인 경우 마지막 문자를 알파벳 S로 교체하고,.. 2025. 2. 16. [백준 3671] 산업 스파이의 편지 (C++) 문제안녕하세요. 저는 산업 스파이입니다. 저의 정체를 절대 다른 사람에게 말하지 말아주세요.저의 가장 최근 일은 유명한 수학 연구소의 최신 연구 결과를 훔쳐오는 것이었습니다. 저는 매우 유능한 산업 스파이이기 때문에, 연구 결과를 어렵지 않게 얻을 수 있었습니다. 하지만, 제가 올 것을 미리 알았는지 연구소에서는 연구 결과를 모두 서류 절단기에 넣어버렸습니다. 어쩔수 없이 저는 눈물을 머금고 종이 조각을 모두 훔쳐왔습니다.저를 고용한 사람은 매우 무서운 사람입니다. 또, 저는 프로이기 때문에 실수를 용납하지 않습니다. 어떻게든 이 종이를 모두 복구해가야합니다. 이 연구소의 연구 주제는 빠른 소인수 분해입니다. 제가 가진 종이 조각에는 숫자가 한 자리씩만 적혀져 있습니다. 원래 숫자가 뭐였는지를 잘 모르겠.. 2024. 12. 30. [백준 6588] 골드바흐의 추측 (C++) https://www.acmicpc.net/problem/6588문제1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.이 추측은 아직도 해결되지 않은 문제이다.백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.각 테스트 케이스는.. 2024. 12. 11. [백준 1456] 거의 소수 (C++) https://www.acmicpc.net/problem/1456문제어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력첫째 줄에 총 몇 개가 있는지 출력한다. 제한1 ≤ A ≤ B ≤ 1014 문제 풀이에라토스테네스의 체를 활용한 문제. sqrt(B)를 초과하는 수에 대해서는 2제곱의 값이 B를 넘어가므로 거의 소수가 존재하지 않는다. 따라서 sqrt(B)까지의 소수들을 에라토스테네스의 체를 이용해 구해 벡터에 저장한다.모든 소수들을 구했다면 벡터의 각 원소(=소수)들에 대해 A와 B .. 2024. 7. 14. 이전 1 다음