에라토스테네스의 체3 [백준] 13206: Professor KCM - JAVA https://www.acmicpc.net/problem/13206 풀이주어진 수들의 최대 공약수를 구해야 한다. 소인수 분해를 통해 각 소수의 최대 개수를 구하고, 이를 계산했다. for (int j = 2; j * j 위의 방식으로 소인수 분해를 했다. 해당하는 소수의 개수를 map배열에 카운트해주었다. 메모리: 314872KB시간: 2580ms언어: Java 11import java.io.*;import java.util.*;public class Main { static final long MOD = 1_000_000_007L; public static void main(String[] args) throws IOException { BufferedReader br = n.. 2024. 6. 10. [알고리즘] 에라토스테네스의 체 - JAVA 내용에라토스테네스의 체는 소수를 찾는 방법 중 하나이다. 1. 2부터 자기 자신을 제외한 2의 배수를 모두 지운다. 2. 남아있는 수 중 3은 소수이므로 3을 제외한 3의 배수를 모두 지운다. 3. 남아있는 수 중 5는 소수이므로 5를 제외한 5의 배수를 모두 지운다. 4. 위의 과정을 반복한다. 코드// N까지의 소수를 구하기 위한 배열boolean[] prime = new boolean[N + 1];// 소수를 false라고 하자// 0과 1은 소수가 아니므로 trueprime[0] = prime[1] = true;// 2부터 자신의 배수를 지운다for (int i = 2; i * i 2024. 5. 11. [백준] 19699: 소-난다! - JAVA https://www.acmicpc.net/problem/19699 풀이소 M마리의 합이 소수인지 판별하는 문제였다. N마리의 소가 있다. N마리 중 M마리의 조합을 만들어 소수인지 판별해주었다. 소수는 에라토스테네스의 체를 구현하여 미리 배열에 정보를 담아놓았다. 오름차순으로 출력과 중복 제거를 위해 TreeSet을 이용했고, Set출력을 위해 Stream을 이용했다. 메모리: 14296KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, M; static int[] cow, group; static boolean[] prime; static TreeSet ans; .. 2024. 5. 11. 이전 1 다음