[CODEGROUND] 나는 소수가 좋아

숫자를 받은 후 소수의 개수를 새어 기약분수로 나타내는 코드이다.

에라토스테네스의 체

참고 : http://marobiana.tistory.com/91

#include <iostream> #include <vector> #include <algorithm> #include <functional> #include <math.h> using namespace std; vector < int > Prime_Number = vector < int >(100001, 1); void check_Prime() { Prime_Number[1] = 0; for (int i = 2; i <= sqrt(100000); i++) { if (Prime_Number[i] == 0) continue; for (int j = i + i; j <= 100000; j += i) Prime_Number[j] = 0; } } int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a%b); } int main() { int for_count, number_count, count; cin >> for_count; check_Prime(); for (int i = 1; i <= for_count; i++) { cin >> number_count; vector < int > number = vector < int >(number_count); for (int k = 0; k < number_count; k++) cin >> number[k]; count = 0; for (int k = 0; k < number_count; k++) { if (Prime_Number[number[k]] == 1) count++; } cout << "Case #" << i << endl; if (count == number_count) cout << 1 << endl; else if (count == 0) cout << 0 << endl; else { int gcd_number; if (max(count, number_count) == count) gcd_number = gcd(count, number_count); else gcd_number = gcd(number_count, count); cout << count / gcd_number << "/" << number_count / gcd_number << endl; } } }