일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- 오버라이딩
- 프로그래머스
- 객체지향
- 멀티프로세싱
- contiune
- break 사용법
- CPU
- 중첩 break
- 캡슐화
- over()
- 입출력
- 붕대 감기
- 티스토리챌린지
- 프로그래머스 붕대 감기
- 오버로딩
- 다형성
- java
- spring security
- continue 사용법
- 오블완
- 자바의 정석
- 리눅스
- 쿠키
- hackerrank
- 붕대 감기 자바
- 멀티태스킹
- 혼공얄코
- SQL Mapper
- spring security 설정
- 자바의정석
- Today
- Total
쉽게 쉽게
[Java] 소수 구하기 본문
▤ 목차
1. 소수 구하기
1. 방법1 (N까지 나누기)
N 보다 작은 자연수들로 나눈 후 소수인지 아닌지 판별하는 알고리즘이다.
시간복잡도: O(N²)
public boolean isPrime(int n) {
if (n <= 1) return false; // 1보다 작으면 false 반환
for (int i = 2; i < n; i++) { // 2보다 크고 n보다 작은 수로 나눈다.
if (n % i == 0) return false; // 만약 나누어 떨어지는 것이 있다면 false 반환
}
return true; // 모두 나누고도 떨어지는 수가 없다면 true 반환
}
2. 방법2 (N의 제곱근보다 작은 수까지 나누기)
첫 번째 방법에서 좀 더 발전된 방법으로 소수를 구할 때 N의 제곱근(√) 까지만 나눈다.
소수인지 판별할 자연수의 제곱근을 기준으로 그 숫자의 약수들의 곱셈은 대칭적으로 곱셈이 일어나기 때문에 제곱근까지만 판별하면 된다.
일 때
- 2×18=36
- 3×12=36
- 4×9=36
- 6×6=36 (제곱근에서 대칭의 끝)
즉, 약수는 작은 수와 큰 수로 짝을 이루고 있으며, 그 짝 중 하나는 항상 √ 보다 작거나 같고, 다른 하나는 √ 보다 크거나 같다.
어떤 수 n이 소수가 아니라면, 최소 하나의 약수는 √ 이하의 범위에 존재해야 한다.
36이 소수인지 확인하려고 한다면, 1부터 √ 36=6 까지만 나누어 보면 된다.
2, 3, 4, 6 중 하나라도 나누어 떨어지면 36은 소수가 아니라고 결론 내릴 수 있다.
왜냐하면, 그 이후에 나오는 약수들은 6보다 큰 값으로, 이미 6 이하에서 발견된 약수와 대칭적으로 대응되기 때문이다.
예를 들어 12는 3에 대응하고, 18은 2에 대응한다.
만약 √ 이하의 값으로 나누어지지 않는다면, 그 이후의 값들로도 나누어지지 않는다.
정리하자면
- 약수는 대칭적으로 존재한다. 예: a×b=n이면, a와 b 중 하나는 반드시 √ 이하다.
- 소수를 확인할 때는 √ 까지의 수만 나눠보면 충분하다. √ 이후의 수로 나누어 떨어질 수 없다면, 그 이전에도 나누어 떨어지지 않았을 것이기 때문이다.
따라서, 소수를 판별할 때는 굳이 그 수 자체까지 나눌 필요 없이 √ 까지만 나누어도 소수인지 아닌지를 알 수 있다.
시간복잡도: O(N√N)
public boolean isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i <= Math.sqrt(n); i++) { // n의 제곱근까지 나누기
if (n % i == 0) return false;
}
return true;
}
3. 방법3 (에라토스테네스의 체)
i = 2 부터 √N 이하까지 반복하여 자연수들 중 i를 제외한 i의 배수들을 제외시키는 방식
먼저 가장 작은 수인 2를 소수로 등록한 후, 2의 배수를 지운다. -> 지우지 않은 수 중 가장 작은 수인 3을 소수로 등록한 후, 3의 배수를 지운다. -> 이를 계속 반복하여 남은 수가 소수이다.
시간복잡도: O(Nlog(log N))
public boolean[] sieveOfEratosthenes(int n) {
//0부터 n까지의 수이기 때문에 n+1을 할당한다.
boolean[] prime = new boolean[n+1];
// 0과 1은 소수가 아니기 때문에 false를 저장한다.
prime[0] = false;
prime[1] = false;
// n의 제곱근까지 나눈다.
for(int i = 2; i <= Math.sqrt(n); i++) {
// 소수라면 뒤에 오는 코드를 스킵한다.
if(prime[i] == true) {
continue;
}
// 2부터 배수에 해당하는 수를 true로 변환한다.
for(int j = i * i; j < prime.length; j = j+i) {
prime[j] = true;
}
}
return prime;
}
잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다. |
'개발공부 > Java' 카테고리의 다른 글
[Java] break, contiune문 사용법 (0) | 2024.11.24 |
---|---|
[Java] Map 메서드 활용법 (0) | 2024.11.19 |
[Java] 최대공약수, 최소공배수 구하기 (0) | 2024.09.20 |
[Java] 약수의 개수 구하기 (0) | 2024.09.15 |
[Java] FILE 업로드(다중) (0) | 2024.04.28 |