[C++学習コードテスト]少数
6274 ワード
エラトステネスの借金
素数を判別するアルゴリズム
任意の自然数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"; //소수인 경우 출력
}
}
}
Reference
この問題について([C++学習コードテスト]少数), 我々は、より多くの情報をここで見つけました https://velog.io/@jy8082/C-코딩테스트-공부-소수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol