[백준] 1978번 소수 찾기 (C++)

문제

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

코드

#include <iostream>

using namespace std;

int main(){
  int n;
  cin >> n;
  int count = n;
  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    if(a==1){
      count -=1;
    }
    for(int j=2; j<a; j++){
      if(a % j == 0){
        count -=1;
        break;
      }
    }
  }
  cout << count;
  return 0;
}

 

더 효율적인 풀이

#include <iostream>
#include <cmath>

using namespace std;

int main(){
  int n;
  cin >> n;
  int count = n;
  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    if(a==1){
      count -=1;
    }
    for(int j=2; j<=sqrt(a); j++){
      if(a % j == 0){
        count -=1;
        break;
      }
    }
  }
  cout << count;
  return 0;
}

정리

소수(prime number)란?

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

 

소수인지 아닌지를 판별하기 위해 주어진 수(위 코드에서는 a)보다 작은 모든 각각의 수들을 주어진 수에 나눠서 단 하나의 경우라도 나누어 떨어지면 소수가 아니고 모든 경우가 나누어 떨어지지 않을 경우 소수임을 이용해 문제를 해결하였다.

 

나의 답 이외의 다른 답이 있는지 궁금해서 구글에 검색한 결과 더 효율적인 코드를 발견했다. for문의 범위를 주어진 수(a)보다 작도록 설정하는 것이 아니라 주어진 수의 제곱근까지 범위를 설정해주면 된다.

 

+ sqrt()

sqrt 안에 있는 매개변수의 제곱근을 구해준다.

<cmath> 헤더 파일에 들어 있다.

 

에라토스테네스의 체란?

고대 그리스의 수학자 에라토스테네스 가 만들어 낸 소수를 찾는 방법이다. 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법이다. 예를 들어 100 이하의 소수를 찾는다고 해보자. 2~100까지 차례대로 탐색할 것이다. 우선 2부터 시작하고 2의 배수들을 모두 제거한다. 그 후 3의 배수를 제거한다. 4의 배수를 제거해야 하는데 4는 이미 2의 배수를 제거할 때 제거되었으므로 건너뛴다. 이러한 과정을 계속 진행하면 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97가 소수임을 구할 수 있다.

 

참조

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 

https://cryptosalamander.tistory.com/26

https://blog.naver.com/ndb796/221233595886

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4