기록

프로그래머스 ‘소수 찾기’ 문제는 주어진 숫자 문자열로 만들 수 있는 모든 수를 조합해, 그중 소수의 개수를 구하는 완전탐색 문제다.처음에는 하나하나 소수 판별을 직접 하는 방식으로 해결할 수 있지만, 더 효율적인 방법은 ‘에라토스테네스의 체’를 활용해 소수 정보를 미리 계산해두는 것이다. url : https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python31. 문제 핵심문자열 numbers로 만들 수 있는 모든 숫자 조합을 생성중복 없이 set에 담고, 그중 소수만 카운팅isPrime()을 수십 번 호출하지 않고, 소수 배열을 미리 캐싱하는 방식으로 개선2. 에라토스테네스의 체def make_sieve(limit): ..

문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 2부터 N까지의 소수를 구하고, Two Pointer 을 이용해서, 합이 N이 되는 경우를 찾는다. 1) 에라토스테네스의 체 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소..