에라토스테네스의 체3 [백준문제풀이] 1644 소수의 연속합 풀이일시 : 2020-12-24 문제 : 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다. 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오... 2021. 1. 3. [백준문제풀이] 1963 소수 경로 풀이일시 : 2020-11-15 문제 : 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: ----- “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야" “그럼 8179로 해” “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.” “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래.. 2021. 1. 2. [기본문제풀이] 에라토스테네스의 체 풀이 일시 : 2020-08-13 에라토스테네스의 체 : 소수(prime number) 판별 알고리즘이다. 어떤 수로도 나뉘어지지 않아야 되기 때문에 그 수를 나눠보면서 판단할 수 있다.. -> 이 방법은 O(N)의 복잡도를 갖는다. 모든 수를 체크했기 때문이다. 제곱근까지만 약수의 여부를 검증한다 -> 이 방법은 O(N^(1/2))로 계산이 가능하다. -> int end = (int)sqrt(x)로 두고 x의 소수를 구하려면 2~end까지 체크한다. 문제 : 에라토스테네스의 체를 이용하여 소수를 출력하여라. 풀이 : 1. 이차원 배열을 생성하여 값을 초기화한다. 2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다. (자신은 지우지않는다.) 3. 3의 배수도 지운다. (자신.. 2020. 12. 28. 이전 1 다음 반응형