Per ardua ad astra.

에라토스테네스의 체(Sieve of Erathosthenes) 개념 지구의 둘레를 처음으로 계산한 고대 그리스 수학자 에라토스테네스(BC273 ~ BC192, Eratosthenes)가 기원전 200년에 고안한 방법으로, 아래와 같은 방법을 이용하여 소수를 구한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1은 소수가 아니라고 했으므로 우선 지워버린다. 다음으로 맨 처음 나오는 수(= 2)는 무조건 소수이다. 왜냐하면 약수가 1과 자기 자신밖에 없기 때문이다. 그리고 2의 배수는 소수가 아니므로 모두 지워버린다. 다음으로 지워지지 않은 수들 중에서 가장 작은 수(= 3)를 찾는다. 이렇게 지워지지 않고 남은 수는 소수이다. 왜냐하면 1이 아니면서 3보다 ..

문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다. 2보다 큰 짝수..

문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다. 입력의 마지막에는 0이 주어진다. 출력 각 테스트 케이스에 대해서, n보다 크고..

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 예제 입력 1 3 16 예제 출력 1 3 5 7 11 13 알고리즘 분류 수학 정수론 소수 판정 에라토스테네스의 체 문제 출처 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 해결 방..

소인수 분해(Prime/Integer Factorization) 개념 특정 자연수를 1보다 큰 자연수인 소인수(소수인 인수)들만의 곱으로 표현하는 것 합성수를 소수의 곱으로 나타내는 방법 소인수 분해를 일의적으로 결정하는 공식은 아직 발견되지 않았다. 현대 암호학에서 소인수 분해는 암호 처리를 하는데 중요하게 사용된다. 모든 합성수는 소인수 분해된 형태를 가지고 있다. 산술의 기본 정리(Fundamental Theorem of Arithmetic)로 증명된다. 알고리즘 기본 알고리즘 소인수는 1이라는 값이 아닌 2부터 시작하는 것이 핵심이며, 2로 나누지 못할 경우 2에서 하나씩 증가시켜주면서 나누어지는지 체크하면 된다. void factorize(int n) { int factor = 2; // 시작 ..

문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 예제 입력 1 72 예제 출력 1 2 2 2 3 3 예제 입력 2 3 예제 출력 2 3 예제 입력 3 6 예제 출력 3 2 3 예제 입력 4 2 예제 출력 4 2 예제 입력 5 9991 예제 출력 5 97 103 알고리즘 분류 수학 정수론 소수 판정 문제 출처 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 ..

문제 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다. 입력 입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다. 출력 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. 예제 입력 1 60 100 예제 출력 1 6..

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 예제 입력 1 4 1 3 5 7 예제 출력 1 3 알고리즘 분류 수학 정수론 소수 판정 에라토스테네스의 체 문제 출처 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 해결 방법 소수 찾기 알고리즘을 사용하여 간단하게 문제를 해결하였다. 소수(Prim..

소수(Prime Number) 약수의 개수를 이용한 소수의 판별 1보다 큰 자연수 중에서 1과 자기 자신 이외에는 약수를 가지지 않는 수, 즉 약수의 개수가 2개인 자연수를 소수(Prime Number)라고 한다. 2의 약수 : 1, 2 3의 약수 : 1, 3 4의 약수 : 1, 2, 4 5의 약수 : 1, 5 6의 약수 : 1, 2, 3, 6 7의 약수 : 1, 7 2, 3, 5, 7, ... 등은 약수의 개수가 2개 이므로 소수이다. 예제 #include using namespace std; int main() { int cnt; for (int i = 2; i