본문으로 바로가기

소수를 구하는 유명한 방법인 에라토스테네스의 체를 이용하여 문제를 해결할 수 있다. 에라토스테네스의 체를 이용하여 소수를 찾는 방법에 대해 잘 모른다면 해당 포스트를 참조하자.

1978: 소수 찾기

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

void f(vector<bool>&, int);// n 이하 정수 중 소수를 찾는 함수

int main() {
  vector<bool> pn(101);// prime number
  fill(pn.begin(), pn.end(), true);
  
  f(pn, 100);// 100이하 자연수 중 소수 판별
  
  int n;
  scanf("%d", &n);
  
  int k = 0;
  while (n--) {
    int x;
    scanf("%d", &x);
    pn[x] == 1 ? k++ : k;// 소수인 것들만 확인해서 카운트한다
  }
  
  printf("%d\n", k);
  return 0;
}

void f(vector<bool>& v, int n) {
  v[1] = false;// 1은 소수가 아니다
  for (int i=2; i<=n; i++) {
    if (!v[i]) continue;
    for (int j=2; j<=n/i; j++) {
      v[i*j] = false;
    }
  }
}

에라토스테네스의 체를 이용하여 소수를 구한다.

2581: 소수

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

void f(vector<bool>&, int);// n 이하 정수 중 소수를 찾는 함수

int main() {
  vector<bool> pn(10001);// prime number
  fill(pn.begin(), pn.end(), true);
  
  int m, n;
  scanf("%d %d", &m, &n);
  
  int sum = 0;
  int min = -1;
  for (int i=2; i<=n; i++) {
    if (!pn[i]) continue;
    
    if (i >= m) {
      sum += i;
      min = min == -1 ? i : min;
    }
    
    for (int j=2; j<=n/i; j++) {
      pn[i*j] = false;
    }
  }
  
  if (min != -1) {
    printf("%d\n", sum);
  }
  
  printf("%d\n", min);
  return 0;
}

마찬가지로 에라토스테니스의 체를 이용하여 소수를 찾되 지정된 범위 내에서 해당 소수를 발견할 경우 최소값과 그 합을 변수에 저장하면 된다.

1929: 소수 구하기

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

void f(vector<bool>&, int);// n 이하 정수 중 소수를 찾는 함수

int main() {
  vector<bool> pn(1000001);// prime number
  fill(pn.begin(), pn.end(), true);
  
  f(pn, 1000000);// 100이하 자연수 중 소수 판별
  
  int m, n;
  scanf("%d %d", &m, &n);
  
  for (int i=m; i<=n; i++) {
    if (pn[i]) {
      printf("%d\n", i);
    }
  }
  
  return 0;
}

void f(vector<bool>& v, int n) {
  v[1] = false;// 1은 소수가 아니다
  for (int i=2; i<=n; i++) {
    if (!v[i]) continue;
    for (int j=2; j<=n/i; j++) {
      v[i*j] = false;
    }
  }
}

에라토스테네스의 체.

베르트랑 공준

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int M = 123456 * 2;

void f(vector<bool>&, int);// n 이하 정수 중 소수를 찾는 함수

int main() {
  vector<bool> pn(M+1);// prime number
  fill(pn.begin(), pn.end(), true);
  
  f(pn, M);// 100이하 자연수 중 소수 판별
  
  int n;
  while (scanf("%d", &n) != EOF) {
    if (!n) break;
    int k = 0;
    for (int i=n+1; i<=2*n; i++) {
      if (pn[i]) k++;
    }
    printf("%d\n", k);
  }
  
  return 0;
}

void f(vector<bool>& v, int n) {
  v[1] = false;// 1은 소수가 아니다
  for (int i=2; i<=n; i++) {
    if (!v[i]) continue;
    for (int j=2; j<=n/i; j++) {
      v[i*j] = false;
    }
  }
}

에라토스테네스의 체.

골드바흐의 추측

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

void f(vector<bool>&, int);// n 이하 정수 중 소수를 찾는 함수

int main() {
  vector<bool> pn(10001);// prime number
  fill(pn.begin(), pn.end(), true);
  
  f(pn, 10000);// 100이하 자연수 중 소수 판별
  
  int t;
  scanf("%d", &t);
  
  while (t--) {
    int n;
    scanf("%d", &n);
    
    int x, y;
    for (int i=n/2; i<=n; i++) {
      if (pn[i] && pn[n-i]) {
        y = i;
        x = n-i;
        break;
      }
    }
    
    printf("%d %d\n", x, y);
  }
  
  return 0;
}

void f(vector<bool>& v, int n) {
  v[1] = false;// 1은 소수가 아니다
  for (int i=2; i<=n; i++) {
    if (!v[i]) continue;
    for (int j=2; j<=n/i; j++) {
      v[i*j] = false;
    }
  }
}

에라토스테네스의 체를 사용하여 우선 소수를 찾고 테스트 케이스에서 주어진 n 값의 절반부터 시작해서 가장 차이가 적은 소수의 쌍을 구하면 된다.


댓글을 달아 주세요