백준 13469 (C++) Older Brother

최초 업로드: 2025-09-03 04:25:52

최근 수정 시간: 2025-09-03 04:26:33

게시자: rlatjwls3333

카테고리: 백준

# [Silver III] Older Brother

[문제 링크](https://www.acmicpc.net/problem/13469)

## 문제 설명

Your older brother is an amateur mathematician with lots of experience. However, his memory is very bad. He recently got interested in linear algebra over finite fields, but he does not remember exactly which finite fields exist. For you, this is an easy question: a finite field of order q exists if and only if q is a prime power, that is, q = pk holds for some prime number p and some integer k ≥ 1. Furthermore, in that case the field is unique (up to isomorphism).

The conversation with your brother went something like this:

## 입력

The input consists of one integer q, satisfying 1 ≤ q ≤ 109.

## 출력

Output “yes” if there exists a finite field of order q. Otherwise, output “no”.

## 풀이
q=1은 예외 처리 해놓고 시작한다.  
2부터 √q까지 소수로 나뉘는지 확인하고 그럴 경우 전부 같은 소수로 이루어졌는지 확인한다.  
만약 √q까지의 소수로 나뉘지 않으면 q 자체가 소수인 것이니 yes를 출력한다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int q; cin >> q;
 if(q==1) {
 cout << "no";
 return 0;
 }

for(int i=2;i*i<=q;i++) {
 if(q%i==0) {
 while(q%i==0) q/=i;
 if(q==1) cout << "yes";
 else cout << "no";
 return 0;
 }
 }
 cout << "yes";
}
```