유클리드 호제법(Euclidean algorithm)
a를 b로 나눈 나머지를 r이라고 했을 때 GCD(a,b) = GCD(b,r) 과 같다.
r이 0일때 b가 최대공약수.
GCD(24,16)=GCD(16,8)=GCD(8,0) = 8
세 수 이상의 최대공약수
GCD(a,b,c) = GCD(GCD(a,b),c)
최소공배수(LCM)
두 수 a,b의 최대공약수가 g라고 하면 LCM = g x (a/g) x (b/g) 이다.
소수(Prime Number)
약수가 1과 자기 자신 밖에 없는 수
= 2~(n-1)로 나누어 떨어지지 않는 수
소수를 구하는 두가지 방법
방법1. 어떤 수 N이 소수인지 아닌지 판별
방법2. N이하의 모든 소수
방법1. 어떤 수 N이 소수인지 아닌지 판별
a. 2~N/2까지의 수로 나누어 떨어지는 지 확인
N까지가 아니라 N/2인 이유는 1을 제외한 가장 작은 약수가 2이고 2에 대응하는 약수가 N/2이기 때문에
가장 큰 약수가 N/2이기 때문이다. 따라서 N/2~N에는 약수가 없다.
이 방법을 쓰면 시간복잡도는 O(N/2) = O(N)
b. 2~√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
📌문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
✍입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
📄출력
주어진 수들 중 소수의 개수를 출력한다.
🌴Code
package math.n1978_소수찾기;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int count = 0;
for (int i=0;i<n;i++) {
int x = sc.nextInt();
boolean flag = true;
if(x==1) continue;
for (int j=2;j*j<=x;j++){ // ❗ j*j주목
if(x%j==0) {
flag = false;
break;
}
}
if(flag==true) count++;
}
System.out.println(count);
}
}
squrt를 사용하지 않고 정수인 j * j를 사용하는 것이 좋음.
시간복잡도는 O(√N)
방법2. N이하의 모든 소수
에라토스테네스의 체
1~N 범위 안에 들어가는 모든 소수를 구할 때 사용
- 2부터 N까지 모든 수를 써 놓는다.
- 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
- 그 수 는 소수이다.
- 이제 그 수의 배수를 모두 지운다. (이때 그 수의 제곱 전까지는 지워져있으므로 제곱 이후의 수부터 지우면 된다.)
에라토스테네스의 체 구현
두개의 배열이 필요
1. 수를 지웠는지 안 지웠는지 판별하는 배열
지웠으면 true, 아니면 false
2. 소수의 목록을 저장하는 배열
1929번_소수구하기
백준링크
시간 제한 2초
📌문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
✍입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
📄출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
👀예제
입력
3 16
출력
3
5
7
11
13
🌴Code
에라토스테네스의 체 이용
package math.n1929_소수구하기;
import java.util.Scanner;
public class prac {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
//수를 지웠는지 안 지웠는지 판별하는 배열
//지웠으면 true, 아니면 false
boolean [] check = new boolean[m+1];
check[0]=check[1] = true;
for (int i=2;i*i<=m;i++){
if(check[i]) continue; //지웠으면 넘어감.
for (int j=i*i;j<=m;j+=i){ // ❗ i의 배수를 하기 위해 i씩 더함.
check[j] = true; //배수를 지워줌.
}
}
for (int i=n;i<=m;i++){
if(!check[i]) System.out.println(i);
}
}
}
for (int j=i*i; j<=m; j+=i){
j = i * i; i의 제곱 전까지는 지워져 있으므로 제곱 이후의 수부터 지우면 되기 때문에 초기값이 i*i의 제곱이다.
j += i; i의 배수를 지워야 하기 때문에 i씩 증가
골드바흐의 추측
- "2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능 "
- 위의 문장에 3을 더하면 "5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다" 로 바뀐다.
(추측이라 칭하는 이유는 10^18이하에서는 증명되어있지만 그 이후는 증명 되지 않았기 때문.)
2보다 큰 짝수 = 소수 + 소수
5보다 큰 홀수 = 소수 + 소수 + 소수
📌문제
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.
✍입력
입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.
각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)
입력의 마지막 줄에는 0이 하나 주어진다.
📄출력
각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.
👀예제
입력
8
20
42
0
출력
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
❓문제풀이
테스트케이스 문제에서 100만 이하의 소수를 구하는 동일한 반복 행위를 하기 때문에 미리 소수를 구해둔다.
소수를 구하기 위해 에라토스테네스의 체를 이용.
소수a + 소수b = 짝수n 이므로 소수a에 미리 구해둔 소수를 차례로 넣고 n-a 가 소수인 지 판별. 이때 에라토스테네스의 체를 이용해 소수를 판별할 때 사용한 boolean 배열을 사용함.
🌴Code
package math.n6588_골드바흐의추측;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static final int MAX = 1000000;
public static void main(String[] args) {
//100만 이하의 소수판별배열 check
boolean [] check = new boolean[MAX+1];
ArrayList<Integer> prime = new ArrayList<>();
check[0] = check[1] = true;
for (int i=2;i*i<=MAX;i++){
if(check[i]) continue;
for (int j=i*i;j<=MAX;j+=i){
check[j] = true;
}
}
//소수리스트 prime
for (int i=0;i<=MAX;i++)
if(!check[i]) prime.add(i);
//골드바흐의 추측 검증
Scanner sc = new Scanner(System.in);
while (true){
boolean flag = false;
int n = sc.nextInt();
if(n==0) break;
for (int i=0;i<prime.size();i++){
int p = prime.get(i);
if(check[n-p]==false){ //❗
System.out.println(n+" = "+prime.get(i)+" + "+(n-p));
flag = true;
break;
}
}
if(!flag)
System.out.println("Goldbach's conjecture is wrong.");
}
}
}
