범위 내 소수 찾기

Seok-Hyun Lee·2020년 7월 26일
1

코드 조각

목록 보기
4/4

코드 전문

#include <iostream>
using namespace std;
int main() {
  int n;
  bool flag = true;
  cin >> n;
  for(int i = 2 ; i <= n; i++){
    for(int j = 2; j*j <= i; j++) // 약수의 거듭제곱 형태로 탐색을 최소화
    {
      if (i % j == 0){
        flag = false;
        break;
      }
    }
    if(flag){
      cout << i;
    }
    else{
      flag = true;
    }
  }
  return 0;
}

설명

소수는 1과 자신을 제외한 수들 중 나누어지지 않아야 한다.
즉, 약수가 1과 자신 밖에 없다

약수

약수는 쌍을 이룬다.
예를 들면, 36 = 1 X 36 , 2 X 18, 3 X 12, 4 X 9, 6 X 6 처럼 말이다.
여기서 우리가 주목할 점은 1, 2 ,3, 4, 6 이다.

약수는 쌍을 이루는 특징을 활용하면 앞의 5가지 숫자 중 1을 제외하고
약수가 나머지는 6 보다 크거나 같은 약수 짝을 가지고 있다.

그래서 약수 존재 여부 탐색은 2 부터 6 까지로 줄어든다.

이것을 일반화 시키면 N 이라는 숫자가 소수인지 확인하기 위해선,
2에서부터 거듭제곱 형태 중 N 보다 작거나 같은 수 중 최대값까지만 탐색하면 된다.

시간복잡도

일반적으로 모든 수를 탐색하여 소수 판단을 하는 경우는 O(N) 만큼 소비된다.
하지만, 위의 방법을 활용하면 O(logN) 으로 소수 판단이 가능하다

profile
Arch-ITech

0개의 댓글