푸으름

Algorithm 공부 #11 - 정수론(소수 구하기&오일러 피) 소수 구하기(에라토스테네스의 체 원리) ● 구하고자 하는 소수의 범위만큼 1차원 배열을 생성 ● 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 숫자의 배수들을 배열에서 모두 지우기 ● 처음으로 선택된 숫자들은 지우지 않고 반복문을 N의 제곱근까지만 돌림 ● 시간 복잡도는 O(Nlog(logN)) 백준 1929번 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ※ N의 범위가 1,000,..

백준 9020번 골드바흐의 추측https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아www.acmicpc.net 정답 코드#include #include #define MAX 1000001 int prime[MAX] = { 1, }; using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); for (int i = 2; i n; int ..

백준 6588번 골드바흐의 추측https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 정답 코드#include #include #define MAX 1000001 using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int prime[MAX] = { 1, }; for (int x = 2; x n; i..

백준 6219번 소수의 자격https://www.acmicpc.net/problem/6219 6219번: 소수의 자격세 정수 A, B, D가 주어진다.www.acmicpc.net 정답 코드#include #include using namespace std; int arr[4000001]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int a,b,k,cnt=0; cin>>a>>b>>k; arr[0]=1; arr[1]=1; for(int x=2;x