#include <iostream>
#include <math.h>
#define N 500
#define N2 199
using namespace std;
bool sosu(int n) {
int k = (int)sqrt(n);
for (int i = 2; i <= k; i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
bool* b = new bool[N + 1]; // 숫자 A을 배열의 A번에 저장하기 위하여 크기 N+1
for (int i = 2; i < N+1; i++) b[i] = true;
for (int i = 2; i * i < N+1; i++) {
for (int k = i * i; k < N+1; k += i) {
b[k] = false;
}
}
// 결과
cout << N << "까지의 소수들\n";
for (int i = 2; i < N + 1; i++) if (b[i]) cout << i << ", ";
cout << "\n\n" << N2 << "는 ";
if (sosu(N2)) cout << "소수입니다.\n";
else cout << "소수가 아닙니다.\n";
return 0;
}
16~23 라인 : N+1만큼의 크기를 갖는 bool 배열을 선언하고 true로 초기화 해준다. 그리고 N까지 i의 배수들을 false로 바꾸는 과정을 반복한다.
7라인 : sosu함수는 인수로 받은 수가 소수인지 판별하여서 참이면 true를 거짓이면 false를 리턴한다.
8라인 : sqrt(n) 함수는 제곱근을 구하는 함수로서 #include <math.h> 를 해주어야 한다.
9라인 : for문을 보면 2부터 n의 제곱근인 k까지 검사한다. k까지만 검사해도 되는 이유는
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
cout << gcd(25, 45) << "\n";
cout << 15*45/gcd(15, 45) << "\n";
return 0;
}
12라인 > gcd 함수는 회귀 함수로서 두 인수 a와 b를 주면 a와 b의 최대공약수를 리턴한다.
