-
소수 (Prime Number)알고리즘 타파/Algorithm 2020. 5. 29. 22:35반응형
참고
https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0)
정의
-
약수가 1과 자기 자신밖에 없는 수
-
어떤 수 N이 소수가 되려면, 2보다 크거나 같아야 하고, N-1보다 작거나 같은 수로 나누어떨어지면 안 된다.
-
예) 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
소수를 찾으려면?
1) N이 소수인지 확인하기 위해 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어본다.
bool prime(int n) { if(n<2) { return false; } for(int i=2; i<=n-1; i++) { if(n%i == 0) { return false; } } return true; }
2) N이 소수인지 확인하기 위해 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어본다.
bool prime(int n) { if(n<2) { return false; } for(int i=2; i<=n/2; i++) { if(n%i == 0) { return false; } } return true; }
3) 에라토스테네스의 체 (Sieve of Eratosthenes)
-
2부터 N까지의 모든 수를 나열한다.
-
2부터 시작하여 2의 배수를 모두 지운다.
-
다음 소수의 배수를 모두 지운다.
int prime[100]; // 소수 저장 int pn=0; // 소수의 개수 bool check[101]; // 지워졌으면 true int n = 100; // 100까지 소수 for (int i=2; i<=n; i++) { if (check[i] == false) { prime[pn++] = i; for (int j = i*i; j<=n; j+=i) { check[j] = true; } } }
반응형'알고리즘 타파 > Algorithm' 카테고리의 다른 글
소인수분해 (Prime Factorization) (0) 2020.07.14 팩토리얼 (Factorial) (0) 2020.05.30 골드바흐의 추측 (Goldbach's conjecture) (0) 2020.05.30 최소공배수 (Least Common Multiple) (0) 2020.05.29 최대공약수 (Greatest Common Divisor) (0) 2020.05.29 -