Create 2.java

ndb796 · web-flow · commit d3fcf11d38f3 · 2020-10-03T21:06:28.000+09:00
diff --git a/20/2.java b/20/2.java
@@ -0,0 +1,27 @@
+import java.util.*;
+
+class Main {
+    public static int n = 1000; // 2부터 1,000까지의 모든 수에 대하여 소수 판별
+    public static boolean[] arr = new boolean[n + 1];
+
+    public static void main(String[] args) {
+        Arrays.fill(arr, true); // 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
+        // 에라토스테네스의 체 알고리즘 수행
+        // 2부터 n의 제곱근까지의 모든 수를 확인하며
+        for (int i = 2; i <= Math.sqrt(n); i++) {
+            // i가 소수인 경우(남은 수인 경우)
+            if (arr[i] == true) {
+                // i를 제외한 i의 모든 배수를 지우기
+                int j = 2;
+                while (i * j <= n) {
+                    arr[i * j] = false;
+                    j += 1;
+                }
+            }
+        }
+        // 모든 소수 출력
+        for (int i = 2; i <= n; i++) {
+            if (arr[i]) System.out.print(i + " ");
+        }
+    }
+}
