수학에서 소수를 찾는 알고리즘
- 특정 범위 내의 소수를 판정하는 데에 효율적
알고리즘
- 찾고 싶은 범위까지의 수 배열을 생성
- 소수가 아닌 1은 제거
- 그 다음 소수인 2를 제외한 2의 배수 제거
- 그 다음 소수인 3을 제외한 3의 배수 제거
- 그 다음 소수인 5를 제외한 5의 배수 제거
- 그 다음 소수인 7을 제외한 7의 배수 제거
.
.
.
에라토스테네스의 체 원리
1) 구하고자 하는 소수의 범위만큼 1차원 배열 생성
2) 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 제거
이때 처음으로 선택된 숫자는 지우지 않음
3) 배열의 끝까지 2번 과정 반복 후 배열에서 남아있는 모든 수 출력
코드
- JAVA
public class Eratos {
public static void main(String[] args) {
// ArrayList로 구현
ArrayList<Boolean> primeList;
// 사용자로부터의 콘솔 입력
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
// n <= 1 일 때 종료
if(n <= 1) return;
// n+1만큼 할당
primeList = new ArrayList<Boolean>(n+1);
// 0번째와 1번째를 소수 아님으로 처리
primeList.add(false);
primeList.add(false);
// 2~ n 까지 소수로 설정
for(int i=2; i<=n; i++ )
primeList.add(i, true);
// 2 부터 ~ i*i <= n
// 각각의 배수들을 지워간다.
for(int i=2; (i*i)<=n; i++){
if(primeList.get(i)){
for(int j = i*i; j<=n; j+=i) primeList.set(j, false);
//i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다.
}
}
StringBuffer sb = new StringBuffer();
sb.append("{");
for(int i=0; i<=n; i++){
if(primeList.get(i) == true){
sb.append(i);
sb.append(",");
}
}
sb.setCharAt(sb.length()-1, '}');
System.out.println(sb.toString());
}
}
M과 N 사이 소수 구하기
import java.io.*;
import java.util.*;
public class Main {
/**
* 소수 구하기 : 에라토스테네스의 체
*
*/
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int A[] = new int[N + 1];
// 0과 1은 소수에서 제외 => 어차피 0이니까 초기화 X
for (int i = 2; i <= N; i++) {
A[i] = i;
}
for (int i = 2; i <= Math.sqrt(N); i++) {
// 소수가 아니면 0으로 체크 -> 넘어감
if (A[i] == 0) continue;
// 어떤 수의 배수 => 소수가 아님 => 0
for (int j = i + i; j <= N; j += i) {
A[j] = 0;
}
}
for (int i = M; i <= N; i++) {
if (A[i] != 0) {
System.out.println(A[i]);
}
}
br.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}- PYTHON
def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
sieve = [True] * n
# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True: # i가 소수인 경우
for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False
# 소수 목록 산출
return [i for i in range(2, n) if sieve[i] == True]시간복잡도
일반적으로 이중 for문을 사용하므로 O(N^2)정도
배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문에 O(Nlog(logN))
Reference
