[자료구조와 알고리즘] 에라토스테네스의 체(소수 찾기)
11495 단어 자료구조와 알고리즘자료구조와 알고리즘
에라토스테네스
: 소수만 걸러져라 (탈탈탈)
📖 에라토스테네스의 체란?
'에라토스테네스의 체'는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다.
에라토스테네스의 체 알고리즘
1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2) 2는 소수이므로 소수 리스트에 2를 추가한다.
3) 자기 자신을 제외한 2의 배수를 모두 지운다.
4) 남아있는 수 가운데 3은 소수이므로 소수 리스트에 3을 추가한다.
5) 자기 자신을 제외한 3의 배수를 모두 지운다.
6) 남아있는 수 가운데 5는 소수이므로 소수 리스트에 5를 추가한다.
7) 자기 자신을 제외한 5의 배수를 모두 지운다.
8) 남아있는 수 가운데 7은 소수이므로 소수 리스트에 7을 추가한다.
9) 자기 자신을 제외한 7의 배수를 모두 지운다.
10) 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
🧠 2부터 시작해서 해당 수가 소수이면 소수 리스트에 추가하고,
그 수의 배수들은 소수가 아니므로 소수 후보에서 제외하는 알고리즘
🧠 2부터 N까지의 수 중에서 소수를 찾는다고 했을 때,
N의 제곱근(나누어 떨어지지 않는다면 N의 제곱근 보다 큰 자연수)보다 작은 소수의 배수를 모두 지우고 남는 수는 모두 소수
💻 에라토스테네스의 체 구현(자바)
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());
}
}
에라토스테네스의 체를 사용하면 숫자 하나 하나 소수 여부를 판별하는 것보다 속도가 빠르다! 소수 판별이 필요할 때는 에라토스테네스의 체를 사용하자!
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());
}
}
에라토스테네스의 체를 사용하면 숫자 하나 하나 소수 여부를 판별하는 것보다 속도가 빠르다! 소수 판별이 필요할 때는 에라토스테네스의 체를 사용하자!
Author And Source
이 문제에 관하여([자료구조와 알고리즘] 에라토스테네스의 체(소수 찾기)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@geesuee/자료구조와-알고리즘-에라토스테네스의-체소수-찾기-ogxglyo3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)