목록Prime Number (8)

코린이의 소소한 공부노트

[프로그래머스/Lv.1] 소수 찾기

1. Input, Output, Example - 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환 - 소수는 약수의 개수가 2개인 자연수를 뜻한다. 2. Constraint 1) n은 2이상 1,000,000이하의 자연수 3. Code import java.util.*; class Solution { public int solution(int n) { boolean[] prime = new boolean[n+1]; Arrays.fill(prime, true); for(int i=2 ; i
코딩테스트 풀이/JAVA 2023. 7. 4. 00:27
[백준 온라인 저지] 6588. 골드바흐의 추측

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. “4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.” 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 1. 입력 - 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다. - 각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000) - 입력의 마지막 줄에는 0이 하나 주어진다. 2. 출력 - 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공..
코딩테스트 풀이/JAVA 2023. 7. 1. 17:05
[백준 온라인 저지] 17103. 골드바흐 파티션

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 두 소수의 순서만 다른 것은 같은 파티션이다. 1. 입력 - 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. 2. 출력 - 각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다. 3. 예제 4. 코드 import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead..
코딩테스트 풀이/JAVA 2023. 6. 22. 12:49
소수(prime number) 판별 알고리즘

1. Problem - 1부터 n까지의 수 중 소수를 찾아보자. 2. Input 1) int n 3. Output 1) [1, n]의 자연수 중 소수를 찾아 출력 4. Explanation 1) 기본 알고리즘 - x는 1부터 n까지의 수 중 하나이다. - 2부터 x-1까지 1씩 증가시켜 가며 x를 나눠본다. 1개라도 x를 나누어 떨어지게 한다면 x는 소수가 아니다. 2) n의 제곱근까지만 찾아보는 알고리즘 - x는 1부터 n까지의 수 중 하나이다. - a*a = x가 되는 a를 구한다. 이때 a가 자연수가 아니라면 소수점 이하를 버린다. - 2부터 a까지 1씩 증가시켜 가며 x를 나눠본다. 1개라도 x를 나누어 떨어지게 한다면 x는 소수가 아니다. 3) 에라토스테네스의 체를 이용한 알고리즘 - 1부터 n..
Back-End/Algorithm 2023. 6. 7. 17:21
[백준 온라인 저지] 11653. 소인수분해

1. 입력 - 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 2. 출력 - N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 3. 예제 4. 코드 import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Int..
코딩테스트 풀이/JAVA 2023. 5. 16. 11:55
[백준 온라인 저지] 4134. 다음 소수

1. 입력 - 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n(0 ≤ n ≤ 4*10^9)이 주어진다. 2. 출력 - 각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다. 3. 코드 import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStream..
코딩테스트 풀이/JAVA 2023. 5. 2. 20:57
[백준 온라인 저지] 4948. 베르트랑 공준

1. 입력 - 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n(1 ≤ n ≤ 123,456)을 포함하는 한 줄로 이루어져 있다. - 입력의 마지막에는 0이 주어진다. 2. 출력 - 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다. 3. 코드 import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new Out..
코딩테스트 풀이/JAVA 2023. 4. 20. 00:21
[백준 온라인 저지] 1929. 소수 구하기

1. 입력 - 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) - M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 2. 출력 - 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 3. 코드 1) 첫 코드(2023/04/20) import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new Output..
코딩테스트 풀이/JAVA 2023. 4. 20. 00:09
이전 Prev 1 Next 다음