- 숫자 N의 소수 판정 방법
1 ~ $\sqrt{N}$까지 N을 나누어 떨어지게 하는 수가 있는지를 확인
- 에라토스테네스의 체 사용하기
각 수는 임의의 값 n * n 제곱하여 나오는 n보다 큰 값을 ( i * i < N )
0과 1은 소수가 아님
boolean 배열을 만들고, 소수가 아닌 값을 탐색하면서 true로 만들기
소수가 아닌 값 처리 시 i*i가 시작인 이유!
-> 5의 경우 5*2 / 5*3 / 5*4 / 5*5 / ... 로 진행되며,
-> 이때 2, 3, 4(2,2)는 앞선 값으로 인해서 소수가 아니라고 처리되기 때문에
10,000까지의 소수의 개수 : 1,229개
private static boolean isPrime(int num) {
if (num < 2) {
// 소수가 아님
return false;
}
if (num == 2) {
// 소수
return true;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
// 소수가 아님
return false;
}
}
// 소수
return true;
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken()); // 소수를 구할 범위
// 소수는 false
boolean[] prime = new boolean[N + 1];
prime[0] = true;
prime[1] = true;
for (int i = 2; i * i <= N; i++) {
// 현재 탐색하는 수(i)가 소수(false)라면
if(!prime[i]) {
// 배수를 소수가 아니(true)라고 처리
// 시작은 자기의 제곱으로 시작
for (int j = i*i; j <= N; j+=i) {
prime[j] = true;
}
}
}
for (int i = 0; i < prime.length; i++) {
if (!prime[i]) {
System.out.print(i +" ");
}
}
}
}
- 소수 기본 문제
https://www.acmicpc.net/problem/1978
- 소수 구하기
https://www.acmicpc.net/problem/1929
- 골드바흐의 추측
https://www.acmicpc.net/problem/9020
※ Hint : 가운데에서부터 양쪽으로 1씩 증감하면서 찾아나가면 된다!
- 신기한 소수
https://www.acmicpc.net/problem/2023
[알고리즘] 구간 합 (부분 합) (0) | 2023.02.10 |
---|---|
[알고리즘] 최대공약수(GCD), 최소공배수 구하기 (유클리드 호제법) (0) | 2023.02.01 |
[알고리즘] 2차원 배열의 회전 (0) | 2023.01.10 |
[코딩테스트] 최단 경로 알고리즘 (0) | 2022.11.23 |
[코딩테스트] 다이나믹 프로그래밍 (0) | 2022.11.22 |