문제 링크입니다: https://www.acmicpc.net/problem/7789
7789번: 텔레프라임
소수를 매우 좋아하는 수학자가 있다. 이 수학자는 매번 전화번호를 받을 때 마다, 그 전화번호가 소수인지 아닌지를 검사한다. 수학자는 자신의 모든 친구의 전화번호가 소수인지 아닌지를 기
www.acmicpc.net
에라토스테네스의 체를 활용하여 풀 수 있는 간단한 문제였습니다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |


개발환경: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 |