소수 판별
소수(prime)란?
1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수를 뜻함 (이때 1은 소수가 아니다)
예) 2, 3, 5, 7, 11, 13 ...
소수 판별 방법
방법1. 숫자 N이 주어질 때, 2 ~ (N - 1) 까지 수 중 나누어 떨어지는 수가 없으면 소수이다
- 1과 자기자신을 제외한 나누어 떨어지는 수가 없어야 소수이므로 반복문을 통해 구하는 가장 간단한 방법
- 시간복잡도 : O(N)
- 단 범위가 너무 클 경우 시간 초과 발생 가능
private static boolean isPrime(int n) {
// 2 ~ n - 1 사이 수 중 나누어 떨어지는 수가 있으면 소수 아님
for(int i = 2; i <= n - 1; i++) {
if(n % i == 0) return false;
}
return true;
}
방법2) 숫자 N이 주어질 때, 2 ~ N의 제곱근까지의 수 중 나누어 떨어지는 수가 없으면 소수이다.
- 시간 복잡도 : O(N^1/2)
약수의 성질
1) 모든 약수 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알수 있다.
2) 따라서 특정 자연 수의 모든 약수를 찾을 때 "가운데 약수(제곱근)"까지만 확인하면 연산 횟수를 줄일 수 있다
16의 약수는 아래와 같고 제곱근인 4 이후로는 대칭성 가지므로, 제곱근까지만 나누어 떨이지는지 확인하여 연산 횟수 줄임
1 2 4 8 16
- 1 * 16
- 2 * 8
- 4 * 4
- 8 * 2
- 16 * 1
private static boolean isPrime(int n) {
// 2 ~ n - 1 사이 수 중 나누어 떨어지는 수가 있으면 소수 아님
for(int i = 2; i <= Math.sqrt(n); i++) {
if(n % i == 0) return false;
}
return true;
}
방법3) 에라토스테네스의 체 알고리즘 사용
- 시간복잡도 O(Nlog(logN))
절차
1) 가장 먼저 소수를 판별할 범위만큼 배열을 할당해 그 인덱스에 해당하는 값을 넣어준다
2) 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다 (이때 1은 소수가 아니므로 제외)
3) 3의 배수를 지울 때 이미 지워진 숫자의 경우 건너뜀 --- 반복
4) 2부터 남아있는 숫자 출력
*참고. 동빈나 강사님 유튜브
https://www.youtube.com/watch?v=5ypkoEgFdH8
*백준 문제(1929번). 소수 구하기
https://www.acmicpc.net/problem/1929
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
해당 문제의 경우 반례가 존재했다.
입력 1 2
출력 2
제출 코드
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static void process() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken()); // M이상
int N = Integer.parseInt(st.nextToken()); // N이하
int[] data = new int[N + 1];
for(int i = 1; i <= N; i++) data[i] = i;
for(int i = 2; i <= N; i++) {
if(data[i] == 0) continue;
for(int j = 2 * i; j <= N; j += i) {
data[j] = 0;
}
}
for(int i = M; i <= N; i++) {
if(i == 1) continue;
if(data[i] != 0) sb.append(i).append("\n");
}
System.out.println(sb.toString());
}
public static void main(String[] args) throws Exception {
process();
}
}
*백준 문제(2960). 에라토스테네스의 체
https://www.acmicpc.net/problem/2960
2960번: 에라토스테네스의 체
2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.
www.acmicpc.net
해당 문제의 경우 소수에 해당하는 숫자도 지우는게 특징이었다.
제출코드
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static void process() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] data = new int[N + 1];
for(int i = 1; i <= N; i++) {
data[i] = i;
}
int cnt = 0;
Loop1 :
for(int i = 2; i <= N; i++) {
if(data[i] == 0) continue;
for(int j = i; j <= N; j += i) {
if(data[j] == 0) continue;
data[j] = 0;
cnt += 1;
if(cnt == K) {
sb.append(j);
break Loop1;
}
}
}
System.out.println(sb.toString());
}
public static void main(String[] args) throws Exception {
process();
}
}
*백준 문제(15965). K번째 소수
https://www.acmicpc.net/problem/15965
15965번: K번째 소수
자연수 K가 주어진다.(1 ≤ K ≤ 500,000)
www.acmicpc.net
- 에라토스테네스의 체를 사용해서 소수를 구하는 것은 동일
- 최대치에서 실수했는데 K 최대치 500,000일때 소수를 알고 배열 크기를 지정해야 한다. (7,368,791)
- 자료 유형에 따라 메모리와 시간이 차이 남을 확인 가능했음
제출코드1. int형 풀이
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int MAX = 7368791;
static void process() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int K = Integer.parseInt(br.readLine());
int[] data = new int[MAX + 1];
for(int i = 2; i <= MAX; i++) {
data[i] = i;
}
for(int i = 2; i <= MAX; i++) {
if(data[i] == 0) continue;
for(int j = i + i; j <= MAX; j += i) {
data[j] = 0;
}
}
int cnt = 0;
for(int i = 2; i <= MAX; i++) {
if(data[i] != 0 && ++cnt == K) {
sb.append(i);
break;
}
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(sb.toString());
bw.flush();
bw.close();
}
public static void main(String[] args) throws Exception {
process();
}
}
제출코드2. boolean형 풀이
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int MAX = 7368791;
static void process() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int K = Integer.parseInt(br.readLine());
boolean[] data = new boolean[MAX + 1];
Arrays.fill(data, true);
for(int i = 2; i <= MAX; i++) {
if(!data[i]) continue;
for(int j = i + i; j <= MAX; j += i) {
data[j] = false;
}
}
int cnt = 0;
for(int i = 2; i <= MAX; i++) {
if(data[i] && ++cnt == K) {
sb.append(i);
break;
}
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(sb.toString());
bw.flush();
bw.close();
}
public static void main(String[] args) throws Exception {
process();
}
}