문제
전화번호 n과 이동 규칙 m이 주어질 때, n과 n + m * 10⁶이 모두 소수인지 판별하라.
입력
전화번호 n과 이동값 m이 주어진다.
출력
둘 다 소수이면 Yes, 아니면 No를 출력한다.
예제
| 입력 | 출력 |
|---|---|
13 2 | Yes |
풀이
두 수 각각에 대해 소수 판정을 수행한다.
isPrime(n)으로 n이 소수인지 확인한다isPrime(n + m * 1000000)으로 변환된 수도 소수인지 확인한다- 둘 다 소수이면
Yes, 아니면No를 출력한다
핵심 아이디어: 각 수에 대해 sqrt(N)까지 나눗셈으로 소수 판정하는 기본 방법을 적용한다.
코드
#include <iostream>
#include <vector>
using namespace std;
bool isPrime(int n)
{
if (n < 2)
return false;
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
int main()
{
int n, m;
cin >> n >> m;
cout << ((isPrime(n) && isPrime(n + m * 1000000)) ? "Yes" : "No");
}복잡도
- 시간: O(sqrt(n + m * 10⁶))
- 공간: O(1)