인프런 커뮤니티 질문&답변

안녕하세요 안뇽ㅎㅎ

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

>> 일단 소수의 범위는 400만으로 해야 합니다. 주어진 수를 이하의 소수를 판단하는 체를 만들어야 하므로.

또한... 소수의 수는 N/2 이하라는 것을 증명해보겠습니다.

자연수 N 이 4이상일 때 유효할 것 같은데요.

1. 기본 사실: 2는 유일한 짝수 소수입니다. 이것은 2보다 큰 모든 짝수가 2의 배수이며, 따라서 소수가 아니라는 것을 의미합니다.

2. 2를 제외한 모든 소수는 홀수: 2를 제외하고, 모든 소수는 홀수입니다. 따라서, 소수를 찾을 때는 홀수만 고려하면 됩니다.

3. 홀수의 수: 1부터 N까지의 숫자 중 홀수의 수는 대략 N/2입니다. 정확히는 N이 홀수인 경우 N/2를 올림한 값, 짝수인 경우 N/2입니다.

4. 소수의 분포: 모든 홀수가 소수인 것은 아니기 때문에, 실제 소수의 개수는 홀수의 개수보다 적습니다. 이는 2를 포함하여 N 이하의 소수의 총 개수가 N/2 이하임을 의미합니다.

따라서, N 이하의 소수의 개수가 N/2 이하임이 증명됩니다.

또한.

def count_primes(n):
    if n < 2:
        return 0
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for i in range(p * p, n+1, p):
                is_prime[i] = False
        p += 1
    return sum(is_prime)

count_primes(4000000)

간단하게 400만 이하의 소수의 갯수를 구하기 위한 스크립트를 짜봤는데요.

약 28만이라는 것을 알 수 있었습니다.

또 에라토스테네스 체에서 i*i크기 까지만 보통 크기 비교 해주는데 다르게 하신 이유도 궁금합니다.

>> 음.. 제 교안에서 체만들 때 i * i 까지한 적은 없습니다. ㅎㅎ

교안내의 에라토스테네스의 채 코드입니다. 참고부탁드립니다.

#include<bits/stdc++.h>
using namespace std; 

const int max_n = 40;
bool che[max_n + 1];
// 예를 들어 40을 넣었을 때 che[40]이 참조가 되므로 max_n + 1을 넣어야 함. 
// max_n까지의 소수를 만드는 함수. 
vector<int> era(int mx_n){ 
    vector<int> v; 
    for(int i = 2; i <= mx_n; i++){
        if(che[i]) continue;
        for(int j = 2*i; j <= mx_n; j += i){ 
            che[j] = 1;
        }
    }
    for(int i = 2; i <= mx_n; i++) if(che[i] == 0)v.push_back(i); 
    return v; 
}
int main(){ 
	vector<int> a = era(max_n);
	for(int i : a) cout << i << " ";
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.