검수요청.png검수요청.png

"소수 (prime number)"의 두 판 사이의 차이

위키원
이동: 둘러보기, 검색
잔글 (→‎같이 보기)
9번째 줄: 9번째 줄:
 
* 2, 3을 제외한 모든 소수는 자연수 n에 대해 6n-1 혹은 6n+1 꼴이다. 역은 성립하지 않는다.
 
* 2, 3을 제외한 모든 소수는 자연수 n에 대해 6n-1 혹은 6n+1 꼴이다. 역은 성립하지 않는다.
  
−
==판별==
+
==예제==
−
* 1은 소수가 아니다.
+
* 에라토스테네스의 체(Sieve of Eratosthenes)
−
* 2는 소수이다.
+
: 1~100까지의 모든 소수를 구한다고 가정했을 때,
−
* 2를 제외한 모든 짝수는 소수가 아니다.
+
# 1은 제거
−
* 1과 자기 자신만이 약수이기 때문에 홀수는 2와 n-1사이에서 약수를 가지지 않는다.
+
# 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
−
 
+
# 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
−
위 과정을 코드로 표현
+
# 지워지지 않은 수 중 제일 작은 5을 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
−
bool isPrime(int n)
+
# 지워지지 않은 수 중 제일 작은 7을 소수로 채택하고, 나머지 7의 배수를 모두 지운다.
−
{''<font color=green> //정수 n이 소수이면 true를 반환한다.</font>''
+
# 지워지지 않고 남은 수는 전부 소수이다.
−
    ''<font color=green> //1은 소수가 아니다.</font>''
+
: {| class="wikitable" width=500 style="color:balck; text-align: center; background-color:#F8F9FA;"
−
    <font color=#006699>if</font>(n == 1)
+
| <del>1 || 2 || 3 || <del>4 || 5 || <del>6 || 7 || <del>8 || <del>9 || <del>10
−
        <font color=#006699>return false</font>;
+
|-
−
     
+
| 11 || <del>12 || 13 || <del>14 || <del>15 || <del>16 || 17 || <del>18 || 19 || <del>20
−
    ''<font color=green> //짝수는 2이면 소수이다.</font>''
+
|-
−
    <font color=#006699>if</font>(n % 2 == 0)
+
| <del>21 || <del>22 || 23 || <del>24 || <del>25 || <del>26 || <del>27 || <del>28 || 29 || <del>30
−
        <font color=#006699>return</font> (n==2);
+
|-
−
         
+
| 31 || <del>32 || <del>33 || <del>34 || <del>35 || <del>36 || 37 || <del>38 || <del>39 || <del>40
−
    <font color=#006699>for</font>(int i=3; i<n; i+=2)
+
|-
−
    {''<font color=green> //2 ~ n-1 범위의 홀수 약수가 있는지 검사한다.</font>''
+
| 41 || <del>42 || 43 || <del>44 || <del>45 || <del>46 || 47 || <del>48 || <del>49 || <del>50
−
        ''<font color=green> //약수가 있다면 소수가 아니다.</font>''
+
|-
−
        <font color=#006699>if</font>(n % i == 0)
+
| <del>51 || <del>52 || 53 || <del>54 || <del>55 || <del>56 || <del>57 || <del>58 || 59 || <del>60
−
            <font color=#006699>return false</font>;
+
|-
−
    }
+
| 61 || <del>62 || <del>63 || <del>64 || <del>65 || <del>66 || 67 || <del>68 || <del>69 || <del>70
−
    ''<font color=green> //약수가 발견되지 않았으므로 소수이다.</font>''
+
|-
−
    <font color=#006699>return true</font>;
+
| 71 || <del>72 || 73 || <del>74 || <del>75 || <del>76 || <del>77 || <del>78 || 79 || <del>80
−
}<ref>김동이, 〈[https://www.opentutorials.org/module/1544/9469 정수론]〉, 《오픈튜토리얼스》, 2015-04-09</ref>
+
|-
 +
| <del>81 || <del>82 || 83 || <del>84 || <del>85 || <del>86 || <del>87 || <del>88 || 89 || <del>90
 +
|-
 +
| <del>91 || <del>92 || <del>93 || <del>94 || <del>95 || <del>96 || 97 || <del>98 || <del>99 || <del>100
 +
|-
 +
|}
  
  

2019년 8월 1일 (목) 10:31 판

소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수를 의미한다. 예를 들어, 자연수 2, 3, 5의 약수는 1과 자기 자신뿐이기 때문에 자연수 2, 3, 5는 소수라고 할 수 있다.

개요

특징

  • 소수는 1보다 큰 자연수이다. 즉, 1은 소수가 아니다.
  • 소수의 약수는 1과 자기 자신뿐이다. 즉, 소수의 약수는 2개뿐이며, 역도 성립한다.
  • 2는 소수이지만, 2를 제외한 모든 짝수는 2를 약수로 가지므로 소수가 아니다.
  • 2, 3을 제외한 모든 소수는 자연수 n에 대해 6n-1 혹은 6n+1 꼴이다. 역은 성립하지 않는다.

예제

  • 에라토스테네스의 체(Sieve of Eratosthenes)
1~100까지의 모든 소수를 구한다고 가정했을 때,
  1. 1은 제거
  2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
  3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
  4. 지워지지 않은 수 중 제일 작은 5을 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
  5. 지워지지 않은 수 중 제일 작은 7을 소수로 채택하고, 나머지 7의 배수를 모두 지운다.
  6. 지워지지 않고 남은 수는 전부 소수이다.
1 2 3 <del>4 5 <del>6 7 <del>8 <del>9 <del>10
11 <del>12 13 <del>14 <del>15 <del>16 17 <del>18 19 <del>20
<del>21 <del>22 23 <del>24 <del>25 <del>26 <del>27 <del>28 29 <del>30
31 <del>32 <del>33 <del>34 <del>35 <del>36 37 <del>38 <del>39 <del>40
41 <del>42 43 <del>44 <del>45 <del>46 47 <del>48 <del>49 <del>50
<del>51 <del>52 53 <del>54 <del>55 <del>56 <del>57 <del>58 59 <del>60
61 <del>62 <del>63 <del>64 <del>65 <del>66 67 <del>68 <del>69 <del>70
71 <del>72 73 <del>74 <del>75 <del>76 <del>77 <del>78 79 <del>80
<del>81 <del>82 83 <del>84 <del>85 <del>86 <del>87 <del>88 89 <del>90
<del>91 <del>92 <del>93 <del>94 <del>95 <del>96 97 <del>98 <del>99 <del>100


각주

참고자료

같이 보기


  검수요청.png검수요청.png 이 소수 (prime number) 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.  

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스
암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산
논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT)
SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512
MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320
기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사
대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES
비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호
영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명
양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜
암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독
암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피
위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반
원본 주소 "http://wiki1.kr/index.php?title=소수_(prime_number)&oldid=118471"