소수

[백준] 2023 - 신기한 소수 (자바 Java)

[Gold V] 신기한 소수 - 2023 문제 링크 성능 요약 메모리: 12856 KB, 시간: 108 ms 분류 백트래킹(backtracking), 수학(math), 정수론(number_theory), 소수 판정(primality_test) 문제 설명 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다. 수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 ..

[백준] 1644 - 소수의 연속합 (자바 Java)

[Gold III] 소수의 연속합 - 1644 문제 링크 성능 요약 메모리: 32812 KB, 시간: 176 ms 분류 수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve), 두 포인터(two_pointer) 문제 설명 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 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이 연속이 아니기에..

[백준] 6588 - 골드바흐의 추측 (자바/Java)

문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다. 각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ..

[백준] 9020 - 골드바흐의 추측 (자바/Java)

문제 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보다 큰 짝수..

[백준] 1929 - 소수 구하기 (자바/Java): 에라토스테네스의 체

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 앞의 문제들처럼 풀었다가 시간 초과가 났다. 에라토스테네스의 체를 사용하는 문제였다. 에라토스테네스의 체는 소수를 구하는 알고리즘으로, 2부터 자기 자신을 제외한 자신의 배수들을 하나씩 지워나가는 알고리즘이다. 이때 끝까지 남아있는 수들이 소수에 해당한다. 그래서 먼저 배열을 선언하여 각 값을 초기화하였다. 이때 index를 그 값으로 사용하기 위해 N+1 크기의 배열을 선언하였다. 그리고 배열을 돌며 값이 0인 경우..

[백준] 2581 - 소수 (자바/Java)

문제 자연수 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을 출력한다. 1978 소수 찾기와 유사하다. 단 소수를 ..

[백준] 1978 - 소수 찾기 (자바/Java)

문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 소수는 1과 자기 자신만을 약수로 갖는 1보다 큰 자연수이다. 그러므로 자기 자신보다 작고 2보다 크거나 같은 수 중에 나머지가 0인 수가 없으면 소수가 된다. 숫자가 1이거나, 약수를 가지는 경우에는 cnt를 더하지 않았고 아닌 경우에만 cnt를 더해 소수의 수를 구하였다. package boj0728; import java.util.Scanner; public class BOJ_1978_소수찾기 { public static void main(..