[C++学習コードテスト]少数

エラトステネスの借金

素数を判別するアルゴリズム
任意の自然数Nに対して最も速くその以下の小数を探す方法

エラトステネスのふるいの原理

1を取り除く.
2以外の2の倍数を取り除きます.
3を除いて、3の倍数を取り除きます.
4を2の倍数に省略します.
5の倍数を除いて・・・
√√Nの倍数を除く.
√√Nが現れるのは、N=A*Bを仮定すると、A、Bともに√Nより大きくならないからである.

C++コード実装

2つの異なる数字を受信し、2つの数字の間の小数を出力するコード.
2つの数字は100000未満です.
(出典:白駿1929号)

#include <iostream>
#include <cmath>


using namespace std;
# define Max 1000000
int main()
{
       ios_base::sync_with_stdio(false); 
       cin.tie(NULL); 
       cout.tie(NULL); 
       int max = 0;
       int min = 0;
       bool Num[Max+1] = {false}; //소수를 판별할 배열 선언
       cin >> min;
       cin >> max;
       Num[0] = Num[1] = true; //0과 1은 소수가 아니기에 판단X
       for(int i = 2; i < sqrt(Max); i++) //2부터 √Max 까지 판단
       {
           if(!Num[i]) //소수가 아닌 배열의 원소만 체크한다(시간 단축)
           {
               for(int j = i * i; j <= Max; j += i)
               //i * k(k<i)까지는 모두 체크완료(ex: 13 >> 12*13까지는 판단완료) 
               {
                   Num[j] = true; //참인경우 소수
               }
           }
       }
       for(int i = min; i<= max; i++)
    {
        if(!K[i])
        {
            cout << i << "\n"; //소수인 경우 출력
        }
    }
    }