백준 1978 / 소수찾기
문제
풀이
1. 소수의 정의를 그대로 이용
n이 소수가 되려면 2보다 크거나 같고, n-1보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.
( 시간 복잡도 : 총 n번 검사하므로 O(n) )
코드
import java.util.Scanner;
public class Num1978 {
static boolean prime(int n) {
if (n < 2) {
return false;
}
for (int i=2; i<=n-1; i++) {
if(n%i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int ans = 0;
while (n-- > 0) {
if(prime(sc.nextInt())) {
ans += 1;
}
}
System.out.println(ans);
}
}
2. n/2로 나누는 방법
n이 소수가 되려면 2보다 크거나 같고, n/2보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.
이유 : N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문
N = a * b로 나타낼 수 있는데, a가 작을 수록 b는 크다.
가능한 a중에서 가장 작은 값은 2이기 때문에, b는 그에 따른 가장 큰 수인 n/2를 넘지 않는다.
( 시간 복잡도 : 총 n/2번 검사하므로 상수항을 무시하기 때문에 결국 O(n) )
코드
static boolean prime(int n) {
if (n < 2) {
return false;
}
for (int i=2; i<=n/2; i++) {
if(n%i == 0) {
return false;
}
}
return true;
}
3. 루트N
n이 소수가 되려면 2보다 크거나 같고, '루트n'보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.
이유 : n이 소수가 아니라면, n = axb로 나타낼 수 있다. ( a<=b )
a > b라면 두 수를 바꿔서 항상 a <= b로 만들 수 있다.
두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.
따라서, 루트 N까지만 검사를 해보면 된다.
( 시간 복잡도 : O(루트n) )
코드
static boolean prime(int n) {
if (n < 2) {
return false;
}
for (int i=2; i*i<=n; i++) {
if(n%i == 0) {
return false;
}
}
return true;
}
출처 : https://www.acmicpc.net/problem/1978
Author And Source
이 문제에 관하여(백준 1978 / 소수찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dogit/백준-1978-소수찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)