![[JAVA] 8. 필수 알고리즘 Ⅵ. 서로소](https://image.inblog.dev?url=https%3A%2F%2Fsource.inblog.dev%2Ffeatured_image%2F2025-02-24T07%3A23%3A12.507Z-12b1f5df-3483-4786-984c-9f3f328c5695&w=3840&q=75)
두 수나 다항식, 집합 등에서 공약수가 1뿐인 경우
예)
- 2와 3
- 9와 10
- 1과 8
- 48과 55
- 연속하는 두 자연수 15, 16
- 두 연속하는 홀수 3, 5
1. 두 수의 약수가 1뿐인지 확인
package algo;
// 서로소
// 두 수의 공약수가 1뿐인 경우
public class Coprime01 {
public static void main(String[] args) {
// 1. 5 와 8은 서로소인가?
int a = 5;
int b = 8;
// 2. a의 약수는?
// 1,5
// 3. b의 약수는?
// 1,2,4,8
// 4. a의 약수 1, | 5,
// b의 약수 1, 2, 4, 8 | 1, 2, 4, 8
// 1
// 공약수는 1뿐
// GCD 최대공약수가 1이라면 서로소인가?
// 8 % 5 = 3;
// 5 % 3 = 2;
// 3 % 2 = 1;
// 2 % 1 = 0;
}
}
2. GCD 최대공약수가 1이라면 두 수는 서로소다.
package algo;
// 서로소
// 두 수의 공약수가 1뿐인 경우
public class Coprime02 {
static int gcd(int n, int m) {
return n % m == 0 ? m : gcd(m, n % m);
}
public static void main(String[] args) {
// 5와 8의 최대공약수 구해보기
int n = 5;
int m = 8;
int a = gcd(n, m);
System.out.println(n + "과 " + m + "의 최대공약수: " + a);
}
}
N값 이하의 서로소 개수 구하기
오일러 피함수
x와 서로소이고 x보다 작은 자연수(음이 아닌 정수)의 개수
예를 들어 Φ(100)은 다음과 같이 구할 수 있다. 100의 소인수는 2와 5이므로, 아래 공식이 성립한다.
1. 전체탐색으로 서로소 개수 구하기
1. N이 12라면
- 1부터 12까지 모든 수를 12와 최대공약수를 비교해 1이면 서로소
package algo;
public class Coprime03 {
static int gcd(int a, int b) {
return a % b == 0 ? b : gcd(b, a % b);
}
public static void main(String[] args) {
int num = 12;
int n = 0;
// 전체탐색으로 num이하의 서로소 찾기
// 서로소는 두 수의 최대공약수가 1이면 그 수는 서로소다
// 1일 경우
// 1은 모든 수와 최대 공약수가 1로 같다.
// 2일 경우
n = 2;
System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
// 3일 경우
n = 3;
System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
// 4일 경우
n = 4;
System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
// 5일 경우
n = 5;
System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
}
}
2. 공통모듈로 만들자
package algo;
public class Coprime03 {
static int gcd(int a, int b) {
return a % b == 0 ? b : gcd(b, a % b);
}
public static void main(String[] args) {
int num = 12;
int n = 1;
// 전체탐색으로 num이하의 서로소 찾기
// 서로소는 두 수의 최대공약수가 1이면 그 수는 서로소다
// 1일 경우
// 1은 모든 수와 최대 공약수가 1로 같다.
// 2일 경우
n++;
System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
// 3일 경우
n++;
System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
// 4일 경우
n++;
System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
// 5일 경우
n++;
System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
}
}
3. 반복문으로 N숫자(12)까지 반복해 보자
package algo;
public class Coprime03 {
static int gcd(int a, int b) {
return a % b == 0 ? b : gcd(b, a % b);
}
public static void main(String[] args) {
int num = 12;
int n = 1;
// 전체탐색으로 num이하의 서로소 찾기
// 서로소는 두 수의 최대공약수가 1이면 그 수는 서로소다
// 1일 경우
// 1은 모든 수와 최대 공약수가 1로 같다.
// 1은 모든 수와 서로소다
// 12-1번 반복
for (int i = 0; i < num - 1; i++) {
n++;
System.out.println(gcd(num, n) == 1 ? n + "은 서로소다" : n);
}
}
}
4. 서로소의 개수를 구해보자
package algo;
public class Coprime03 {
static int gcd(int a, int b) {
return a % b == 0 ? b : gcd(b, a % b);
}
public static void main(String[] args) {
int num = 12;
int n = 1;
int count = 1;
// 전체탐색으로 num이하의 서로소 찾기
// 서로소는 두 수의 최대공약수가 1이면 그 수는 서로소다
// 1일 경우
// 1은 모든 수와 최대 공약수가 1로 같다.
// 1은 모든 수와 서로소다
// 12-1번 반복
for (int i = 0; i < num - 1; i++) {
n++;
if (gcd(num, n) == 1) {
count++;
System.out.println(n + "은 서로소다");
} else {
System.out.println(n);
}
}
System.out.println(count + "개");
}
}
2. 오일러 피함수로 서로소 개수 구하기
1. N의 값이 12라면, 12의 약수를 구한다.
- 12약수는 1~12까지의 수 중 12%n==0을 성립하는 n이다.
- 1, 2, 3, 4, 6, 12
package algo;
import java.util.ArrayList;
import java.util.List;
public class Coprime04 {
public static void main(String[] args) {
// 숫자 1은 제외한다.
// 1. 12의 약수 구하기
List<Integer> list = new ArrayList();
int n = 12;
for (int i = 2; i <= n; i++) {
if (12 % i == 0) {
list.add(i);
}
}
System.out.println("1을 제외한 12의 약수들");
System.out.println(list);
}
}
2. 각 약수들이 소수인지 판별
- 약수의 개수가 2개면 소수, 1과 자기자신
package algo;
import java.util.ArrayList;
import java.util.List;
public class Coprime04 {
public static void main(String[] args) {
// 숫자 1은 제외한다.
// 1. 12의 약수 구하기
List<Integer> list = new ArrayList();
int n = 12;
for (int i = 2; i <= n; i++) {
if (12 % i == 0) {
list.add(i);
}
}
// 2. 약수가 소수인지 확인하기
for (int number : list) {
int count = 0;
for (int i = 1; i <= number; i++) {
if (number % i == 0) {
count++;
}
}
if (count == 2) {
System.out.println(number + "는 소수다");
}
}
}
}
3. 오일러 피함수 공식 사용
package algo;
import java.util.ArrayList;
import java.util.List;
public class Coprime04 {
public static void main(String[] args) {
// 숫자 1은 제외한다.
// 1. 12의 약수 구하기
List<Integer> list = new ArrayList();
int n = 12;
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
list.add(i);
}
}
// 2. 약수가 소수인지 확인하기
List<Integer> sosuList = new ArrayList();
for (int number : list) {
int count = 0;
for (int i = 1; i <= number; i++) {
if (number % i == 0) {
count++;
}
}
if (count == 2) {
sosuList.add(number);
}
}
// 3. 오일러 피함수 사용하기
double num = 1;
for (double number : sosuList) {
num *= 1 - (1 / number);
}
System.out.println((int) (num * n) + "개");
}
}
4. 소인수분해를 사용해 오일러 피함수 적용
package algo;
import java.util.ArrayList;
import java.util.List;
public class Coprime06 {
public static void main(String[] args) {
// 12를 소인수 분해
int round = 0;
int n = 12;
int NUMBER = n;
int 나누는수 = 2;
int 승수 = 0;
List<Integer> 나누는수list = new ArrayList<>();
List<Integer> 승수list = new ArrayList<>();
System.out.println("n = " + n);
while (true) {
round++;
if (n % 나누는수 == 0) {
n = n / 나누는수;
승수++;
} else {
if (승수 != 0) {
승수list.add(승수);
나누는수list.add(나누는수);
나누는수 = 나누는수 + (n % 나누는수);
승수 = 0;
} else {
나누는수 = 나누는수 + (n % 나누는수);
}
if (n == 1) break;
}
}
System.out.println("소인수들 = " + 나누는수list);
// 소인수를 사용한 오일러 피함수 적용
double num = 1;
for (double number : 나누는수list) {
num *= 1 - (1 / number);
}
System.out.println("서로소의 개수 = " + (int) (NUMBER * num) + "개");
System.out.println("반복횟수 = " + round);
}
}
N값 이하의 서로소 값 찾기
1. N이 12인 경우
package algo;
import java.util.ArrayList;
import java.util.List;
public class Coprime05 {
static int gcd(int n, int m) {
return n % m == 0 ? m : gcd(m, n % m);
}
public static void main(String[] args) {
int n = 12;
// 12 이하의 자연수에서 서로소인 값을 찾아보자
List<Integer> 서로소들 = new ArrayList();
for (int i = 1; i <= n; i++) {
// 최대공약수가 1이면 서로소다
if (gcd(n, i) == 1) {
서로소들.add(i);
}
}
System.out.println(서로소들);
}
}
Share article