알고리즘/BOJ

백준 7789번 텔레프라임

꾸준함. 2021. 6. 17. 21:09

문제 링크입니다: https://www.acmicpc.net/problem/7789

 

7789번: 텔레프라임

소수를 매우 좋아하는 수학자가 있다. 이 수학자는 매번 전화번호를 받을 때 마다, 그 전화번호가 소수인지 아닌지를 검사한다. 수학자는 자신의 모든 친구의 전화번호가 소수인지 아닌지를 기

www.acmicpc.net

에라토스테네스의 체를 활용하여 풀 수 있는 간단한 문제였습니다.

 

#include <iostream>
using namespace std;
const int MAX = 10000000;
int minFactor[MAX];
void eratosthenes(void)
{
minFactor[0] = minFactor[1] = -1;
for (int i = 2; i < MAX; i++)
{
minFactor[i] = i;
}
for (int i = 2; i*i < MAX; i++)
{
if (minFactor[i] == i)
{
for (int j = i * i; j < MAX; j += i)
{
if (minFactor[j] == j)
{
minFactor[j] = i;
}
}
}
}
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int pastNumber, additionalNumber;
cin >> pastNumber >> additionalNumber;
int newNumber = pastNumber + additionalNumber * 1e6;
eratosthenes();
if (minFactor[pastNumber] == pastNumber
&& minFactor[newNumber] == newNumber)
{
cout << "Yes\n";
}
else
{
cout << "No\n";
}
return 0;
}
view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

백준 7947번 Koncert  (1) 2021.06.19
백준 7891번 Can you add this?  (0) 2021.06.18
백준 7700번 아즈텍 피라미드  (0) 2021.06.16
백준 7601번 Outfits  (2) 2021.06.15
BOJ 7598번 Bookings  (0) 2021.06.12