[알고리즘] 소수 구하기 - JavaScript

2022. 8. 23. 15:46·알고리즘/풀이 힌트
목차
  1.  소수 ? 
  2. 소수를 구하는 방법 
  3. 2부터 N - 1까지 루프를 돌며 나눠보기 
  4. 제곱근으로 확인하기 
  5. 에라토스테네스의 체
반응형

 소수 ? 

1 또는 자기 자신만을 약수로 가지는 수를 의미한다. 

 

소수를 구하는 방법 

2부터 N - 1까지 루프를 돌며 나눠보기 

소수를 구할 때 가장 먼저 생각할 수 있는 방법으로 O(n) 시간 복잡도를 가진다. 

function is_prime(num) {
    for (let i = 2; i < num; i += 1) {
        if(num % i === 0) {
            return false;
        }
    }
    
    return true
}

다른 소수 구하는 방법에 비해 느린편에 속한다. 

 

제곱근으로 확인하기 

어떤 소수라도 N의 제곱근보다 큰 수로 나눠지지 않는다는 공식을 이용한다. 

시간 복잡도는 O(sqrt(n)) 으로 훨씬 빠른 방법이다. 

function is_prime(num) {
    for (let i = 2; i * i < num; i += 1) {
        if(num % i === 0) {
            return false;
        }
    }
    
    return true
}

에라토스테네스의 체

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 

범위안의 숫자 중에 몇개의 소수가 있는지 알고 싶을때 자주 사용한다. 

예를 들어 30까지에서 알고 싶은 경우 

처음 2를 소수에 넣고 2의 배수를 전부 지운다. 

다음으로 3을 소수에 넣고 3의 배수를 전부 지워준다. 

4는 2의 배수라서 넘어가고 5를 소수에 넣고 5의 배수를 전부 지워준다. 

6부터는 제곱이 30보다 크기때문에 끝나서 지워진 숫자 외 모든 숫자가 소수가 된다. 

 

function get_primes(num) {
    const prime = [false, false, ...Array(num - 1).fill(true)];
    
    for(let i = 2; i * i <= num; i += 1) {
        if(prime[i]) {
            for(let j = i * 2; j <= num; j += i) {
                prime[j] = false;
            }
        }
    }
    
    return prime.filter(Boolean);
}
반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘 > 풀이 힌트' 카테고리의 다른 글

[알고리즘] 재귀 함수를 이용한 트리 순회 알고리즘  (1) 2022.08.26
[알고리즘] 재귀함수 - JavaScript  (0) 2022.08.25
[알고리즘] 이진 탐색 - JavaScript  (0) 2022.08.17
[알고리즘] 트라이 - JavaScript  (1) 2022.08.15
[알고리즘] 힙 - JavaScript  (1) 2022.08.13
  1.  소수 ? 
  2. 소수를 구하는 방법 
  3. 2부터 N - 1까지 루프를 돌며 나눠보기 
  4. 제곱근으로 확인하기 
  5. 에라토스테네스의 체
'알고리즘/풀이 힌트' 카테고리의 다른 글
  • [알고리즘] 재귀 함수를 이용한 트리 순회 알고리즘
  • [알고리즘] 재귀함수 - JavaScript
  • [알고리즘] 이진 탐색 - JavaScript
  • [알고리즘] 트라이 - JavaScript
잉여개발자
잉여개발자
풀스택 개발자를 목표로 잉여롭게 개발 공부도 하면서 다양한 취미 생활도 즐기고 있는 잉여 개발자입니다.
  • 잉여개발자
    잉여로운 개발일지
    잉여개발자
    • 분류 전체보기 (789)
      • 개발정보 (36)
      • 개발환경 (7)
      • 개발생활 (19)
      • React (141)
        • 이론 (23)
        • 기능 (12)
        • 실험실 (88)
        • 버그 (6)
        • 패스트캠퍼스 (9)
        • Npm (3)
      • React Native (28)
        • 공통 (6)
        • TypeScript (3)
        • JavaScript (18)
        • 버그 (1)
      • Next.js (30)
        • 이론 (13)
        • 실험실 (13)
        • 버그 (3)
      • Web (35)
      • 알고리즘 (202)
        • 풀이 힌트 (39)
      • JavaScript (47)
      • TypeScript (29)
        • 기초 (27)
        • 실험실 (2)
      • Node.js (13)
        • 이론 (0)
        • 기능 (3)
        • 실험실 (9)
        • 버그 (1)
      • 도커 (4)
      • CCNA (22)
        • 이론 (4)
        • 문제 (18)
      • 취미생활 (167)
        • 잉여로운 칵테일 (2)
        • 잉여의 식물키우기 (130)
        • 잉여로운 여행기 (11)
        • 잉여의 제2외국어 (21)
        • 잉여로운 책장 (2)
      • Java (1)
        • Java의 정석 (1)
      • 꿀팁 공유 (3)
  • 태그

    영어회화
    알고리즘
    덤프
    타일러영어
    바질 키우기
    ReactNative
    CCNA
    리얼학습일기
    typescript
    next.js
    다이소
    ChatGPT
    리액트
    타입스크립트
    Docker
    바질
    redux
    Babel
    리얼클래스
    네이버 부스트캠프
    식물
    네트워크
    Node.js
    프로그래머스
    자바스크립트
    javascript
    webpack
    react
    CSS
    영어독학
  • hELLO· Designed By정상우.v4.10.1
잉여개발자
[알고리즘] 소수 구하기 - JavaScript

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.