문제 풀이 전 이론 - 1
- 소수는 약수가 1과 자기 자신 밖에 없는 수이다.
- N이 소수이기 위해서는 N/(2-(N-1))이 0으로 나누어 떨어져서는 안된다.
- 소수를 구하는 방법은 두가지가 있다.
- 1. 어떤 수 N이 소수인지 아닌지를 판별한다.(효율성을 크게 안따져도 되는 경우)
- 2. N이하의 모든 소수를 다 구한다.(N의 맥시멈이 100만이어서 미리 저장해놓아야 하는 경우)
- 해당 문제는 N의 최악의 경우가 치명적이지 않으므로 첫 번째 방법을 사용해보겠다.
문제 풀이 전 이론 - 2
- 어떤 수 N이 소수인지 아닌지를 판별하기 위해서는 N을 2~N-1로 나누었을 때 0이 나오는지 살펴보면 된다.
- 하지만, 굳이 N-1까지 반복해볼 필요도 없다. 약수 파트에서 살펴보았듯이 약수는 대칭 관계가 있기 때문에 $\sqrt{N}$까지만 반복해보면 된다.
public class Main {
public static void main(String[] args) {
int a, n, cnt =0; // 개수
boolean array[];
Scanner scan = new Scanner(System.in);
a = scan.nextInt();
array = new boolean[a];
for(int i = 0; i < array.length; i++) {
n = scan.nextInt();
array[i] = primenum(n);
}
for(int i =0; i < array.length; i ++) {
if(array[i] == true) {
cnt++;
}
}
System.out.print(cnt);
}
public static Boolean primenum(int n) {
if(n < 2) {
return false;
}
for(int i = 2; i*i <= n; i++) { // 루트n까지만 반복해서 구함
if(n % i == 0) {
return false;
}
}
return true;
}
}
출력
문제로부터 얻어간 것
소수에는 약수 이론이 포함되어 있기 때문에 약수에서 배웠던 이론을 사용할 수 있었다. 굳이 N까지 나눠보지 않더라도 $\sqrt{N}$까지만 나누면 충분히 약수를 알 수 있다는 것이다. 그리고 $\sqrt{N}$은 i*i<=n으로 대체하여 정수 표현을 사용하는 것도 좋은 방법이다.
느낀점
해당 문제는 N의 최악의 경우가 시간 제한에 치명적이지 않기 때문에 첫 번째 방법을 이용하여 어렵지 않게 풀었지만, 만약 시간 제한이 치명적이라면 두 번째 방법을 사용해야 할 것이다. 이를 통해 실행 시간을 미리 예측하여 어떤 방법으로 풀지 고민해보는게 매우 중요한 것임을 알았다.
'기타등등 > 알고리즘 기록' 카테고리의 다른 글
[JAVA] 백준 6588 - 골드바흐의 추측 (0) | 2021.02.24 |
---|---|
[JAVA] 백준 1929 - 소수 찾기2 (에라토스테네스의 체) (0) | 2021.02.24 |
[JAVA] 백준 2609 - 최대공약수와 최소공배수(유클리드 호제법) (0) | 2021.02.24 |
[JAVA]백준 17425 - 약수의 합 (0) | 2021.02.20 |
[JAVA]백준 17427 - 약수의 합2 (0) | 2021.02.18 |