{% embed url=“https://www.acmicpc.net/problem/1978” %}
Solution 1.
•
17812 kb / 216 ms
•
풀이
◦
역시 에라토스테네스의 체를 이용해서 풀었다.
◦
초기에 입력값을 배열로 저장하려는 시도를 했지만, 풀이를 진행하면서 굳이 그럴 필요가 없다는 것을 알게 되었고, 이내 입력을 받자마자 바로 소수 배열 내 존재여부를 체크하는 방향으로 코드를 수정하였다.
package practice.algorithm.math;import java.util.Scanner;public class Bj1978_1 { public static boolean[] isPrime = new boolean[1001]; public static void main(String[] args) { isPrime(); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int count = 0; while(n > 0) { if (!isPrime[sc.nextInt()]) { count++; } n--; } System.out.println(count); } private static void isPrime() { //true : 소수 아님, false : 소수임 isPrime[0] = isPrime[1] = true; for (int i = 0; i < Math.sqrt(isPrime.length); i++) { if (!isPrime[i]) { for (int j = i*i; j < isPrime.length; j += i) { isPrime[j] = true; } } } }}
Java
복사
Solution 2.
•
17748 kb / 220 ms
•
제곱근을 이용한 기본 판별법
package practice.algorithm.math;import java.util.Scanner;public class Bj1978_2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int count = 0; for (int i = 0; i < n; i++) { boolean isPrime = true; int num = sc.nextInt(); if (num == 1) continue; for (int j = 2; j <= Math.sqrt(num); j++) { if (num % j == 0) { isPrime = false; break; } } if (isPrime) { count++; } } System.out.println(count); }}
Java
복사