728x90
반응형
1. 가설 적용 코드 (C++)
typedef unsigned long long ll;
/*
* input : ll input (정수)
* output : int (1 or 0)
* unsigned long long 형태의 정수를 넣으면 해당 수가 소수인지 여부를 알려준다.
* 소수 판별 custom 버전
*/
int is_prime_number_custom(ll input)
{
if (input < 2) {
return 0;
}
for (ll j = 2; j <= (ll)(input / j); j++)
{
if (input % j == 0)
{
return 0;
}
}
return 1;
}
2. 가설 적용 코드 (Python)
def func1(input):
if input < 2:
return 0
for j in range(2, int(input/j)+1):
if input % j == 0:
return 0
return 1
3. 에라토스테네스의 체 (c++)
/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(int m) {
bool* arr = new bool[m + 1];
memset(arr, 1, sizeof(bool) * (m+1));
arr[0] = false;
arr[0] = false;
for (int i = 2; i < m + 1; i++) {
if (arr[i] == true) {
for (int j = i * 2; j < m + 1; j += i) {
arr[j] = false;
}
}
}
return arr;
}
4. 최소 공배수, 최대 공약수
int func_2609_gcd(int a, int b) {
if (a % b == 0) {
return b;
}
else {
return func_2609_gcd(b, a % b);
}
}
int func_2609_lcm(int a, int b) {
return (a * b) / func_2609_gcd(a, b);
}
728x90
반응형
'코딩테스트 > 알고리즘' 카테고리의 다른 글
[자료구조] 우선순위 큐 - 작성 중 (0) | 2022.04.11 |
---|---|
[알고리즘] 하노이의 탑 (0) | 2022.03.09 |
[알고리즘] DFS/ BFS (0) | 2022.02.05 |
[알고리즘] 달팽이 배열 채우기 (0) | 2021.11.06 |
[알고리즘] 0 ~ N 사이의 소수 개수 구하기 (2) | 2020.05.19 |
[알고리즘] RSA 암복호화 알고리즘 C로 구현하기? (2) | 2020.05.17 |
댓글