전체 글

BOJ17103.java-주어진 수의 골드바흐파티션 갯수 구하기 최대입력정수 1,000,000까지의 소수정보를 담은 check[]를 먼저 생성. 인덱스가 false이면 인덱스의 수가 소수, true이면 소수가 아닌 수이다. 골드바흐파티션에서 순서가 바뀐 한 쌍은 하나로 세기 때문에, 주어진 수의 절반까지만 반복문을 적용한다. 2부터 주어진 수의 절반까지 1씩 증가하며, 해당 수와 (주어진 수 - 해당 수)가 소수인지 확인한다. 해당 수와 (주어진 수 - 해당 수)가 모두 소수이면 골드바흐파티션이므로, 카운트를 증가시킨다. import java.util.Scanner; public class BOJ17103 { public static void main(String[] args) { Scanner sc =..

복잡한 알고리즘을 단순하게. 기존: 반복문의 i가 5의 배수일 때 하나씩 추가하고, i가 5를 인수로 2개이상 가지고 있는지 판단함. 5단위로 n까지 진행함. 신규: (반복문의 i) 나누기 (5)의 몫을 추가하고, 5를 한번 더 곱한 수로 또 나누고 추가함. 5제곱단위로 n까지 진행함. import java.util.Scanner; public class BOJ1676 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int sum = 0; for (int i = 5; i

골드바흐의 추측 구현하기, 에라토스테네스의 체 사용함 에라토스테네스의 체를 사용하여 백만까지의 소수를 구한다. 그리고 2부터 원하는 짝수 사이에서, 합이 원하는 짝수가 되는 두 소수를 구한다. 골드바흐의 추측에서, 같은 수를 두 번 더하는 경우도 허용한다. import java.util.Scanner; public class BOJ6588 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); boolean[] primeFalse=new boolean[1000001]; primeFalse[1]=true; for(int i=2;i

작은 수의 팩토리얼 직접 구현하기 import java.util.Scanner; public class BOJ10872 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int fact=1; while(n>1){ fact*=n--; } System.out.println(fact); } }

isChecked[]의 해당 인덱스(=실제 수)가 소수인지 검사 후, 소수가 아니면 true로 바꾼다. 입력이 최대 백만이므로, 배열의 사이즈는 백만+1 이다. Boolean 배열의 기본값은 false이므로, 소수를 false로 저장한다. 소수인 수를 찾으면, 그 수의 배수들을 모두 true로 바꾼다. 이때, 정석대로라면 '소수*소수' 부터 반복문을 돌며 true로 바꿔야 하지만, Integer의 범위를 넘어가는 경우가 생기므로, '소수*2' 부터 true로 바꿔준다. 저장된 배열에서 false인 인덱스를 출력하면, 소수를 출력하는 것과 같다. import java.util.Scanner; public class BOJ1929 { public static void main(String[] args) { ..

주어진 100개 이하의 1000이하 자연수에서 소수찾기 한 개의 수를 검증하는 가장 빠른 방법인 자연수 x의 루트값 이하에서 나누어지는 수가 있는지 확인하는 방법을 사용. import java.util.Scanner; public class BOJ1978 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t=sc.nextInt(); int cnt=0; while(t-->0) { int x = sc.nextInt(); if(primeNumber(x)){ cnt++; } } System.out.println(cnt); } public static boolean primeNumber(int x){ if(x