소수 판정

(2020-03-14)

소수 찾기

1. 소수의 판정

  ㅇ 에라토스테라스의 체(Eratosthenes' Sieve)가 유명
     - (2부터 시작하여, 모든 정수배수를 체로 거르는 방법)

  ㅇ 에라토스테라스 체 구현 例)
     - (자바스크립트)
        
function eratosthenes(n) {
    var p = [];
    for (var i=2; i<=n; i++) p[i] = true; // 2 ~ n까지의 모든 정수를 일단 소수로 간주
    var max = Math.floor(Math.sqrt(n)); // 소수 x는 √n까지 구하면 됨
    var x = 2; // 최초의 소수
    while (x <= max) { // √n 즉, max까지 반복
        for (var i = 2 * x; i <= n; i += x) p[i] = false; // x의 배수들을 합성수로 처리
        while(!p[++x]) /* empty */ ; // 다음 소수 x를 찾음
    }
    return p;
} 
소수 판정 구현 例) - (개요) . 2 부터 시작하여 제곱근 보다 작은 수 까지, 나누어 떨어지지 않으면 소수로 판정 - (C 언어)
int is_prime (int n) {
    int i;
    if (n < 2) return 0;
    for (i = 2; i*i < n; i++) {  // i < n or i < n/2 or i*i < n
        if (n % i == 0) return 0;
    }
    return i;
}
- (자바 언어)
public static boolean isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i*i < n; i++)  // i < n or i < n/2 or i*i < n
        if (n % i == 0) return false;
    return true;
}


[(기타 알고리즘)] 1. 소수 판정 2. 하노이 탑
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 순서도
            3. 재귀 호출
        1.   알고리즘 효율성
        2.   알고리즘 종류
        3.   알고리즘 전략
        4.   (기타 알고리즘)
          1.   1. 소수 판정
              2. 하노이 탑
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

 
        최근수정     요약목록     참고문헌