소수 찾기
문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
4
1 3 5 7
출력
주어진 수들 중 소수의 개수를 출력한다.
3
내 코드
package com.heejin.baekjoon.ex09;
import java.util.Scanner;
public class No1978 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
boolean[] sosus = sosus(1, 1000);
int num = sc.nextInt();
int count = 0;
for (int i = 0; i < num; i++) {
int a = sc.nextInt();
if (!sosus[a - 1]) {
count++;
}
}
System.out.println(count);
}
static boolean[] sosus(int min, int max) {
boolean[] whole = new boolean[max - min + 1];
if (min == 1) {
whole[0] = true;
}
for (int i = 2; i <= max; i++) {
for (int j = 2; j <= max / 2 ; j++) {
if (i * j > max) {
break;
}
if (i * j >= min) {
whole[i * j - min] = true;
}
}
}
return whole;
}
}
파이썬으로 소수 문제들을 풀었을 때의 기억을 되짚어봤을 때, 소수를 구하는 방법은 소수의 정의를 그대로 따르는 방법, 즉 범위에 있는 모든 수에 1과 자기자신을 제외한 어떤 자연수로도 나눠떨어지지않는 지를 확인하는 방법, 그리고 에라토스테네스의 체....즉 범위에 있는 모든 수의 집합에서 자기자신을 제외한 2이상의 배수(2*2, 2*3, 2*4, 2*5..... 3*2, 3*3, 3*4, 3*5,....4*2, 4*3, 4*4, 4*5.....)들을 모두 제외하고 남은 수의 집합을 구하는 방법이 있다. 전자는 직관적이긴 해도, 백준 문제를 풀다보면 시간 초과라든지 메모리 초과라든지 뭐든 뜨게 된다. 확인하는 모든 수를 대상으로 그것이 그 이하의 수로 나눠떨어지는 지 모두 확인해야하기 때문이다. 가령 수를 한개만 확인하더라도 그 수가 엄청 크다면 2 이상 그 수 이하의 모든 수로 나누는 과정을 거쳐야한다. 따라서 후자가 전자보다 더 효율적일 수 있다.
내 기억에는 이 문제는 전자의 방법으로 얼마든지 풀 수 있었던 것 같다. 근데 어차피 후자의 방법으로 풀어야할 날이 올 것이기 때문에 처음부터 후자를 택했다. 내가 구현한 sosus라는 메서드는 최솟값 이상 최댓값 이하의 수들 중 소수가 아닌 것을 true로, 소수인 것을 false로 저장된 배열을 리턴한다. 소수인 것을 true로 소수가 아닌 것을 false로 할 수도 있었지만 일일이 모든 자리의 값을 true로 지정하기 싫었다.
아무튼 만약 5 이상 10이하의 수들 중에 소수를 구한다면 sosus(5, 10)는 [false, true, false, true, true, true] 배열을 리턴한다.
whole[0] | whole[1] | whole[2] | whole[3] | whole[4] | whole[5] |
5 | 6 | 7 | 8 | 9 | 10 |
false | true | false | true | true | true |
그런데 만약 최솟값이 1이라면 1은 소수가 아니기 때문에 1을 먼저 true로 변경하는 과정이 필수적이다.
이 문제에서는 일단 범위가 1이상 1000이하으로 주어졌기 때문에 sosus(1, 1000)의 리턴 배열을 받고 시작한다. 그리고 입력값들을 여러개 받으면 받은 배열에서 그의 값에 해당하는 인덱스 값이 false일 경우 count 를 하나씩 올리는 방식으로 답을 구한다.
'자바 자료구조 & 알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글
백준 2581번 - 소수 (0) | 2020.09.04 |
---|---|
백준 1712번 - 손익분기점 (0) | 2020.08.26 |
백준 1011번 - Fly me to the Alpha Centauri (0) | 2020.08.26 |