위키원
"소수 (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:12 판
소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 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은 제거
- 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
- 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
- 지워지지 않은 수 중 제일 작은 5을 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
- 지워지지 않은 수 중 제일 작은 7을 소수로 채택하고, 나머지 7의 배수를 모두 지운다.
- 지워지지 않고 남은 수는 전부 소수이다.
12 3 45 67 891011 1213 14151617 1819 20212223 242526272829 3031 323334353637 38394041 4243 44454647 484950515253 545556575859 6061 626364656667 68697071 7273 747576777879 80818283 848586878889 9091929394959697 9899100
- 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]
각주
참고자료
- 〈소수 (수론)〉, 《위키백과》</ref>
- 수학방 공식 홈페이지 - https://mathbang.net/199
- 김동이, 〈정수론〉, 《오픈튜토리얼스》, 2015-04-09
- 〈2. 소수 구하기 - 에라토스테네스의 체〉, 《위키독스》
- 신매력, 〈[C++ 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체]〉, 《티스토리》, 2013-09-29
- 신매력, 〈[JAVA 소수 구하기 최적의 알고리즘 (1)]〉, 《티스토리》, 2013-09-20
같이 보기
이 소수 (prime number) 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.
