목록에라토스테네의 체 (1)

알고리즘 모음(C++)

백준 1644 - 소수의 연속합(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 에라토스테네스의 체 + 두 포인터가 합쳐진 문제였습니다. 1 ~ N까지의 수에서 소수를 판정한 뒤, 해당 소수의 값들로 N을 만들 수 있는지 확인하면 되는 문제였습니다. N의 범위가 최대 4,000,000 이여서 N*N크기의 2중 for문을 돌린다면 시간 초과가 생길 수 있습니다. 따라서 에라토스테네스의 체를 사용해주시면 됩니다. 소수 판정이 끝났다면 소수가 있을 때와 소수가 없을 때로 나누어서 계산해야합니다.(소수가 없을 때를 고려하지 않아 계속 런타임 에러가 생겼습니다..) 소수가 없을 때에는 ..
백준 2021. 11. 2. 18:18
이전 Prev 1 Next 다음