[BOJ] 4948번 베르트랑 공준

복기

에라토스테네스의 체는 boolean 배열을 이용하여 구한다.

코드

• C++ 17

#include <iostream>   #define LENGTH  1024 * 256   using namespace std;   int N; bool Primes[LENGTH] = { false }; int CountOfPrimes[LENGTH] = { 0 };   int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);       // 에라토스테네스의 체로 소수를 구한다.     Primes[0] = Primes[1] = true;     for (size_t i = 2; i < LENGTH; i++)     {         if (Primes[i])             continue;           for (size_t j = i * 2; j < LENGTH; j += i)             Primes[j] = true;     }       // 베르트랑 공준은 아래의 점화식으로 구할 수 있다.     // B(N) = P(2 * N) - P(N)     // P(n)은 n 이하에서의 소수의 개수다.     // 따라서 소수의 개수를 구해준다.     for (size_t i = 2; i < LENGTH; i++)     {         // 소수의 개수는 아래의 점화식과 같다.         // P(N) = (N is prime) ? P(N - 1) + 1 : P(N - 1)         CountOfPrimes[i] = CountOfPrimes[i - 1];         if (Primes[i] == false)             ++CountOfPrimes[i];     }       while (true)     {         cin >> N;         if (N == 0)             break;           cout << CountOfPrimes[2 * N] - CountOfPrimes[N] << '\n';     } }

• C# 6.0

using System;   namespace Csharp {     class Program     {         static readonly int LENGTH = 1024 * 256;           static int N;         static bool[] Primes = new bool[LENGTH];         static int[] CountOfPrimes = new int[LENGTH];           static void Main(string[] args)         {             Primes[0] = Primes[1] = true;             for (int i = 2; i < LENGTH; i++)             {                 if (Primes[i] == true)                     continue;                   for (int j = i * 2; j < LENGTH; j += i)                     Primes[j] = true;             }               for (int i = 2; i < LENGTH; i++)             {                 CountOfPrimes[i] = CountOfPrimes[i - 1];                 if (Primes[i] == false)                     ++CountOfPrimes[i];             }               while (true)             {                 N = Convert.ToInt32(Console.ReadLine());                 if (N == 0)                     break;                   Console.WriteLine(CountOfPrimes[2 * N] - CountOfPrimes[N]);             }         }     } }

• Python 3

from sys import stdin input = stdin.readline   LENGTH = 262144 primes = [ False ] * LENGTH primes[0] = primes[1] = True   for i in range(2, LENGTH):     if primes[i]:         continue       for j in range(i * 2, LENGTH, i):         primes[j] = True   countOfPrimes = [0] * LENGTH for i in range(2, LENGTH):     countOfPrimes[i] = countOfPrimes[i - 1]     if primes[i] == False:         countOfPrimes[i] += 1      while True:     n = int(input())     if n == 0:         break          print(countOfPrimes[2 * n] - countOfPrimes[n])