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

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

위키원
이동: 둘러보기, 검색
47번째 줄: 47번째 줄:
 
     int i = 2;
 
     int i = 2;
 
   
 
   
     // 입력받은 수 만큼 배열에 모두 초기화 해둔다
+
     ''<font color=green>// 입력받은 수 만큼 배열에 모두 초기화 해둔다.</font>''
 
   
 
   
 
     for (i = 2; i <= num; i++) {
 
     for (i = 2; i <= num; i++) {
54번째 줄: 54번째 줄:
 
      
 
      
 
     for (i = 2; i <= num; i++) {  
 
     for (i = 2; i <= num; i++) {  
         if (arr[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다
+
         if (arr[i] == 0) ''<font color=green>// 이미 체크된 수의 배수는 확인하지 않는다.</font>''
 
             continue;
 
             continue;
         for (int j = i + i; j <= num; j += i) { // i를 제외한 i의 배수들은 0으로 체크
+
         for (int j = i + i; j <= num; j += i) { ''<font color=green>// i를 제외한 i의 배수들은 0으로 체크</font>''
 
             arr[j] = 0;
 
             arr[j] = 0;
 
         }
 
         }
 
     }
 
     }
 
   
 
   
     // 출력
+
     ''<font color=green>// 출력</font>''
 
   
 
   
 
     for (i = 2; i <= num; i++) {
 
     for (i = 2; i <= num; i++) {
67번째 줄: 67번째 줄:
 
             cout << arr[i] << " ";
 
             cout << arr[i] << " ";
 
     }
 
     }
  }
+
  }<ref>신매력, 〈[https://marobiana.tistory.com/91 [C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체]〉, 《티스토리》, 2013-09-29</ref>
 +
 
 +
* JAVA
 +
public class PrimeNumber1 {
 +
  public static void getPrime(int num, ArrayList<Integer> prime) {
 +
    prime.add(2);
 +
 +
    for (int i = 2; i <= num; i++) {
 +
      for (int j = 0; prime.size() > j; j++) {
 +
        if (i % prime.get(j) == 0) break; ''<font color=green>// 소수가 아닌 경우 pass</font>''
 +
 +
        if (j + 1 == prime.size()) ''<font color=green>// 소수일 때</font>''
 +
              prime.add(i);
 +
        }
 +
      }
 +
 +
      for (Integer result : prime) {
 +
          System.out.println(result);
 +
      }
 +
  }
 +
 +
  public static void main(String[] args) {
 +
      ArrayList<Integer> prime = new ArrayList<Integer>();
 +
 +
      long start = System.currentTimeMillis();
 +
      getPrime(30000, prime);
 +
      long end = System.currentTimeMillis();
 +
      System.out.println("수행시간 : " + (end - start));
 +
  }
 +
}<ref>신매력, 〈[https://marobiana.tistory.com/91 [JAVA] 소수 구하기 최적의 알고리즘 (1)]〉, 《티스토리》, 2013-09-20</ref>
 +
 
 +
 
  
 
{{각주}}
 
{{각주}}
76번째 줄: 107번째 줄:
 
* 김동이, 〈[https://www.opentutorials.org/module/1544/9469 정수론]〉, 《오픈튜토리얼스》, 2015-04-09
 
* 김동이, 〈[https://www.opentutorials.org/module/1544/9469 정수론]〉, 《오픈튜토리얼스》, 2015-04-09
 
* 〈[https://wikidocs.net/21638 2. 소수 구하기 - 에라토스테네스의 체]〉, 《위키독스》
 
* 〈[https://wikidocs.net/21638 2. 소수 구하기 - 에라토스테네스의 체]〉, 《위키독스》
 +
* 신매력, 〈[https://marobiana.tistory.com/91 [C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체]〉, 《티스토리》, 2013-09-29
 +
* 신매력, 〈[https://marobiana.tistory.com/91 [JAVA] 소수 구하기 최적의 알고리즘 (1)]〉, 《티스토리》, 2013-09-20
  
 
==같이 보기==
 
==같이 보기==

2019년 8월 1일 (목) 11:11 판

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

개요

특징

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

예제

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

   // 입력받은 수 만큼 배열에 모두 초기화 해둔다.

   for (i = 2; i <= num; i++) {
       arr[i] = i;
   }
   
   for (i = 2; i <= num; i++) { 
       if (arr[i] == 0) // 이미 체크된 수의 배수는 확인하지 않는다.
           continue;
       for (int j = i + i; j <= num; j += i) { // i를 제외한 i의 배수들은 0으로 체크
           arr[j] = 0;
       }
   }

   // 출력

   for (i = 2; i <= num; i++) {
       if (arr[i] != 0)
           cout << arr[i] << " ";
   }
}[2]
  • JAVA
public class PrimeNumber1 {	
  public static void getPrime(int num, ArrayList<Integer> prime) {
    prime.add(2); 
	
    for (int i = 2; i <= num; i++) {
      for (int j = 0; prime.size() > j; j++) {
        if (i % prime.get(j) == 0) break; // 소수가 아닌 경우 pass
			
        if (j + 1 == prime.size()) // 소수일 때
             prime.add(i);
        }
     }
     for (Integer result : prime) {
         System.out.println(result);
     }
  }
	
  public static void main(String[] args) {
     ArrayList<Integer> prime = new ArrayList<Integer>();

     long start = System.currentTimeMillis();
     getPrime(30000, prime);
     long end = System.currentTimeMillis();
     System.out.println("수행시간 : " + (end - start));
  }
}[3]


각주

  1. 김동이, 〈정수론〉, 《오픈튜토리얼스》, 2015-04-09
  2. 신매력, 〈[C++ 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체]〉, 《티스토리》, 2013-09-29
  3. 신매력, 〈[JAVA 소수 구하기 최적의 알고리즘 (1)]〉, 《티스토리》, 2013-09-20

참고자료

같이 보기


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