문제
해결 방안 고민
•
소수는 2부터 시작하여 자기 자신을 제외한 다른 수와 나누어 떨어지면 안 된다.
•
소수를 구분할 수 있는 boolean 변수가 필요할 것 같다.
•
System.out.println() 보다는 다른 출력 방식으로 출력하는 것을 고민해본다.
해결 방법
•
BufferedReader 를 사용하여 입력을 받는다.
•
isPrime 이라는 불리언 변수를 선언하여 소수를 구분한다.
◦
2부터 소수의 제곱근까지 순회하는 반복문을 만들고 소수의 조건에 부합하는 수를 카운트해주면 된다.
•
출력은 BufferedWriter 를 사용한다.
◦
단 출력할 때 String.valueOf() 을 활용하여 count를 형변환해줘야 한다.
코드
import java.io.*;
import java.util.*;
// 소수 찾기 - 브론즈 II
public 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));
br.readLine();
int count = 0;
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
while (st.hasMoreTokens()) {
boolean isPrime = true;
int prime = Integer.parseInt(st.nextToken());
if (prime == 1) {
continue;
}
for (int i = 2; i <= Math.sqrt(prime); i++) {
if (prime % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
count++;
}
}
bw.write(String.valueOf(count));
bw.flush();
bw.close();
br.close();
}
}
Java
복사
소수에 대하여
•
소수란 1과 자기 자신으로만 나누어지는 수를 의미한다.
•
소수를 구할 수 있는 3가지 방법을 정리해본다.
직접 구현
•
N 보다 작은 자연수들로 나누는 방식
•
N 이하의 모든 소수 출력
public static void Prime(int num) {
if (num < 2) // 0과 1은 소수가 아님
return;
else if (num == 2) { // 2는 소수
System.out.println(num);
return;
}
for (int i = 2; i < num; i++) {
if(num % i == 0) // 소수가 아닐 경우
return;
}
// 위 반복문에서 약수를 갖고 있지 않는 경우 소수
System.out.println(num);
return;
}
Java
복사
Math.sqrt() 메소드 사용
•
√N 이하의 자연수들로 나누는 방식
•
sqrt() : 제곱근
•
제곱근 이하로 범위가 줄어드는 이유
◦
소수 판별할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 발생하기 때문
•
N 이하의 모든 소수 출력
public static void Prime(int num) {
if (num < 2) // 0과 1은 소수가 아님
return;
else if(num == 2) { // 2는 소수
System.out.print(num);
return;
}
for(int i = 2; i <= Math.sqrt(num); i++) {
if(num % i == 0) // 소수가 아닐 경우
return;
}
// 위 반복문에서 약수를 갖고 있지 않는 경우 소수
System.out.print(num);
return;
}
Java
복사
에라토스테네스의 체
•
i = 2 부터 √N 이하까지 반복하여 자연수들 중 i를 제외한 i의 배수들을 제외시키는 방식
•
N 이하의 모든 소수 구하기
public class OutputPrime {
public static boolean[] prime; // 소수를 체크할 배열
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
Prime(N);
for (int i = 0; i < prime.length; i++) {
if(prime[i] == false) { // 소수(false)일 경우 출력
System.out.println(i);
}
}
}
// N 이하 소수 생성 메소드
// 소수면 false, 소수가 아니면 true
public static void Prime(int N) {
prime = new boolean[N+1]; // 0 ~ N
prime[0] = prime[1] = true; // 숫자 0과 1은 소수가 아님
if (N < 2) // N이 1 이하일 경우
return;
// √N(제곱근) 이하까지 반복
for (int i = 2; i <= Math.sqrt(N); i++) {
if(prime[i] == true) // 이미 한번 체크된 배열이면 continue
continue;
// i의 배수라면 소수가 아니므로 true
for (int j = i * i; j < prime.length; j = j+i) {
prime[j] = true;
}
}
}
}
Java
복사