Programing/Algorithm

에라토스테네스의 체를 이용한 소수 찾기

2016. 5. 17. 19:50
반응형
- 해당하는 모든 소수를 출력하라.
소수란 1과 자기 자신만을 약수로 가지는 수이다. 100이하의 자연수 중 모든 소수를 출력하시오.

소수를 오름차순으로 출력한다. 각 출력값 사이는 공백으로 구분하고 출력값 5개 마다 줄바꿈을 한다.

아래와 같은 결과 값이 출력되어야 한다.

2 3 5 7 11 
13 17 19 23 29 
31 37 41 43 47 
53 59 61 67 71 
73 79 83 89 97

 

위 내용까지 트라이캐치의 소수 찾기 문제이며, 아래코드는 오름차순과 출력값 사이를 공백으로 구분하고, 5개마다 줄바꿈을 적용하지 않은 소스이다.

 

해당 코드는 범용성을 위해 자바스크립트를 이용하여 만들었으며, 에라토스테네스의 체를 이용한 방법이다.

function getPrimesUpTo(n) {
    if (n < 2) return [];

    // true는 소수로 간주되는 초기 상태
    const isPrime = new Array(n + 1).fill(true);
    isPrime[0] = false;
    isPrime[1] = false;

    for (let i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            // i의 배수들을 모두 false 처리
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 인덱스가 true인 숫자만 필터링하여 소수 목록 생성
    const primes = [];
    for (let i = 2; i <= n; i++) {
        if (isPrime[i]) primes.push(i);
    }

    return primes;
}

// 예시 사용
console.log(getPrimesUpTo(100)); // 100 이하의 모든 소수 출력
 

 

아래는 재귀 함수를 이용하여 좀더 간략하게 구성
function sieve(arr, primes) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] % primes[0] === 0 && arr[i] !== primes[0]) {
            arr.splice(i, 1);
            i--; // 중요: 삭제 후 인덱스 조정
        }
    }
    primes.shift();
    if (primes.length === 0) arr.shift(); // 1 제거

    return primes.length === 0 ? arr : sieve(arr, primes);
}

const numbers = Array.from({ length: 100 }, (_, i) => i + 1);
const primesToUse = [2, 3, 5, 7]; // 100 이하라면 sqrt(100) 이하 소수만 필요
console.log(sieve(numbers, [...primesToUse]));

 

 

에라토스테네스의 체에 대한 부연설명

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

아래 움직이는 이미지를 통해 쉽게 알고리즘을 눈으로 확인하자.

 

 

 

반응형
저작자표시 비영리 동일조건 (새창열림)

'Programing > Algorithm' 카테고리의 다른 글

jvascript array 경우의 수 구하기 (permute)  (0) 2022.02.15
LRU Cache (Least Recently Used) / 프로그래머스 캐시  (0) 2022.01.19
콜라츠 추측  (0) 2021.08.27
하샤드의 수 (Harshad Number)  (0) 2021.08.25
덧셈 뺄셈 동적 계산 (dynamic plus minus, Dynamic addition and subtraction)  (0) 2019.07.19
주민등록번호 체계 및 유효성 검사 (javascript)  (2) 2016.10.07
퀵 정렬(Quick Sort) (javascript)  (0) 2016.05.31
재귀 함수를 이용한 거듭제곱 (a의 n승) (javascript)  (0) 2016.05.18
'Programing/Algorithm' 카테고리의 다른 글
  • 덧셈 뺄셈 동적 계산 (dynamic plus minus, Dynamic addition and subtraction)
  • 주민등록번호 체계 및 유효성 검사 (javascript)
  • 퀵 정렬(Quick Sort) (javascript)
  • 재귀 함수를 이용한 거듭제곱 (a의 n승) (javascript)
Dongkkase
Dongkkase
개발자로 일하면서 부딪히는 문제풀이가 누군가에게 도움이 되길 바라며
    반응형
  • Dongkkase
    정집사의 개발로그
    Dongkkase
  • 전체
    오늘
    어제
    • All (463) N
      • 금융 (61)
      • Programing (284) N
        • Algorithm (39) N
        • API (2)
        • javascript (121)
        • CSS (8) N
        • HTML (10)
        • PHP (15)
        • JAVA (27)
        • JSP (17)
        • JSP 예제 (1)
        • IOS (1)
        • Android (1)
        • Sencha Touche (1)
        • bat file, cmd (0)
        • 디버깅 (2)
        • SQL (17)
        • MS-SQL (1)
        • MySQL (12)
      • Server (14)
        • Docker (1)
        • Windows (9)
        • Linux (3)
        • jeus (1)
      • Database (6) N
      • IT 일반 (15)
      • 리뷰 (1)
        • Book (17)
        • 제품 (2)
        • 영화 소개 (11)
        • 음악 소개 (7)
      • 잡생각 (32) N
        • 회고 (3) N
        • 자료실 (6)
        • 낙서장 (12)
        • 위시리스트 (2)
        • WOW (1)
        • 덕 (1)
  • 인기 글

  • 최근 댓글

  • 태그

    읽고 싶은 책
    IT블로그
    블로그
    자바스크립트
    IT·컴퓨터
    기초
    디자인패턴
    자바스크립트유틸
    jsp
    JavaScript
    자바
    SQL
    Java
    iT's MY LiFE
    사고 싶은 책
    js패턴
    위시리스트
    IT 관련
    It
    php
Dongkkase
에라토스테네스의 체를 이용한 소수 찾기
상단으로

티스토리툴바