[C++] 유한소수 판별하기

 

유한소수 판별하기

두 정수 a와 b가 매개변수로 주어질 때, a/b가 유한소수이면 1을, 무한소수라면 2를 return하도록 solution 함수를 완성해주세요.

 

분자와 분모의 최대공약수로 분모를 나눈 뒤, 그 분모가 2, 5 가 아닌 소수로 나눠지면 무한소수, 아니라면 유한소수입니다.

 

#include <string>
#include <vector>
#include <cmath>

using namespace std;

// 소수 구하기 O(log n)
bool isPrime2(int n) {
	for (int i = 2; i <= n; i++) { // 2~n의 제곱근까지
		if (n%i == 0) { // i가 n의 약수라면 소수가 아니므로 false return
			return false;
		}
	}
	return true;  // 2 ~ n-1까지 약수가 없다면 소수이므로, true return
}



// 삼항 연산자를 사용해서 참이면 최대공약수인 b를 return, 아니면 재귀를 사용해서 gcd(b, a % b) 반복
int gcd(int n, int m){ 
    return m ? gcd(m, n % m) : n;
}


int solution(int a, int b) {
    int answer = 0, gcd_num;
    gcd_num = gcd(a, b);
    b /= gcd_num;
    for(int i = 3; i <= b; i++){
        if(b % i == 0 && i != 5 && isPrime2(i)) return 2;
    }
    return 1;
}

 

 

 

+ 최대공약수를 이용한 최소공배수 구하기

 

// 삼항 연산자를 사용해서 참이면 최대공약수인 b를 return, 아니면 재귀를 사용해서 gcd(b, a % b) 반복
int gcd(int n, int m){ 
    return m ? gcd(m, n % m) : n;
}


// 최소공배수는 두 수의 곱을 최대공약수로 나누면 된다
int lcm(int n, int m) {
    return n * m / gcd(n, m);
}

 

 

 

소수판별

[알고리즘] 소수판별 알고리즘 C++

 

에라토스테네스의 체

C++ 백준 BOJ 2960 에라토스테네스의 체