소수찾기

Programming/BaekJoon

[JAVA] 백준 9020번 : 골드바흐의 추측

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net ㅇ 문제 입력한 수를 만족하는 소수의 합을 구하는 문제이다. 소수를 찾아야 하니 에라토스테네스의 체를 이용해여 접근한다. ◆ 핵심 아이디어 1. 입력값까지의 소수를 구해야 한다. 2. 입력값의 소수의 합을 출력한다. 3. 소수의 합(골드바흐 파티션)이 여러 개일 경우, 두 소수의 차이가 가장 적은 것을 출력한다. 4. 소수는 작은 것부터 출력한다. ◆ 에라토스테네스의 체 htt..

Algorithm

[Algorithm] JAVA 소수판별 - 에라토스테네스의 체

ㅇ 소수란? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 예를 들어 10보다 작은 소수는 2, 3, 5, 7이 있다. ㅇ 소수 찾기 소수를 찾는 방법은 총 3가지가 있다. 1. N을 N보다 작은 자연수로 모두 나누기 2. N의 제곱근보다 작은 자연수로 모두 나누기 3. 에라토스테네스의 체 이용하기 ㅇ N보다 작은 자연수로 나누기 첫번째 방법은 매우 간단하면서 기초적인 방법이다. N보다 작은 수로 모두 나누어 만약 나누어 떨어지는 것이 없다면 N은 소수일 것이다. 예를 들어보자. 만약 6이 주어졌을 때 1보다 크고 6보다 작은 수, 2, 3, 4, 5로 모두 나누어보자. 6 / 2 = 3 6 / 3 = 2 6 / 4 = 1 ... 2 6 / 5 = 1 ... 1 6은 2와 3으로 나누어 떨어..

Meezzi
'소수찾기' 태그의 글 목록