#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) 으로 소수 판단이 가능하다