参照ビデオ:https://youtu.be/CyINCmJPjfM
素数とは、1より大きい自然数のうち、1と自分だけが弱い数を持つ自然数のこと.ここで、約数は任意の数を分ける0ではなく整数であるため、最終的には、1より大きい自然数の中で、1と自分で分ける自然数しかない.1自分以外の自然数と分けると、その数は少数ではないと判断できます.

6は1,2,3,4に分かれており、少数ではありません.

7は1と7を除いて離れず少数です.

きほんアルゴリズム

#include<iostream>
using namespace std;

bool isPrimeNumber(int x) {
    if (x < 2) // 소수의 정의에서 벗어난 수들은 예외 처리
        return false;
        
    // 2부터 (x-1)까지의 모든 수를 확인하며
    for (int i = 2; i < x; i++) {
        // x가 해당 수로 나누어 떨어진다면
        if (x % i == 0) {
            return false; // i는 x의 약수이고, x는 소수가 아님.
        }
    }
    
    return true;
}

int main(){
    cout << isPrimeNumber(3) << '\n'; // 1 
    cout << isPrimeNumber(4) << '\n'; // 0 

    return 0;
}

上記のコードは2から(x−1)までのすべての自然数を逐一チェックするので,時間複雑度はO(n)である.すなわち,少数の数値であることを確認するには,それに比例する時間が必要である.たとえば、10億が少数であることを判別するには、2から(10億-1)までのすべての数字に対して演算を実行する必要があります.

薬性

上記の方法よりも効率的なアルゴリズムを実現するためには,約数が持つ性質を考慮することができる.すべての約数には,中間約数を準対乗算対称とする性質がある.例えば、16の約数は1、2、4、8、16であり、このとき2*8=8*2=16であるので、約数間の乗算が対称であることがわかる.
したがって、特定の自然数のすべての薬水を見つけるには、中間の薬水(平方根)を確認するだけでよい.例えば、16を2で割ることは8で割ることを意味するので、16のすべての薬水はより速い速度で得ることができる.

改善されたアルゴリズム

約数の性質を用いて素数判別アルゴリズムを改良した.2から(x−1)ではなく,xの平方根を決定すればxの約数を求めることができる.次に、xが小数であるかどうかを決定します.

#include<iostream>
#include<cmath>
using namespace std;

bool isPrimeNumber(int x) {
    if (x < 2) // 소수의 정의에서 벗어난 수들은 예외 처리
        return false;
        
    // 2부터 x의 제곱근까지 모든 수를 확인하며
    for (int i = 2; i <= (int)sqrt(x); i++) {
        // x가 해당 수로 나누어 떨어진다면 
        if (x % i == 0) {
            // i와 그에 대칭인 수는 모두 x의 약수이고, x는 소수가 아님.
            return false; 
        }
    }
    
    return true;
}

int main(){
    cout << isPrimeNumber(15) << '\n'; // 0

    return 0;
}

2からxの平方根(小数点を無視)までのすべての自然数を演算し,このアルゴリズムの時間複雑度はO(nsqrt{n}n)である.

多数少数の判別

上記のアルゴリズムを用いて「1つの数」が小数であるか否かを判別することができる.ただし、特定の数の範囲内に存在するすべての小数を検索するにはどうすればいいですか?この場合,エラトネスのふるいアルゴリズムを用いることができる.

エラトネスのボリュームアルゴリズム

多数の自然数を少数か否か判別する際に用いられる代表的なアルゴリズムである.

において、テストステロンのふるいは、N以下のすべての小数を探すために使用することができる.

具体的な動作過程は以下の通りである.

2からNまでのすべての自然数をリストします.

処理されていない最小数iは、

の残りの数で検索される.

余り(i自身を除く)からiの倍数を除去する.

これ以上繰り返されないまで、2、3回のプロセスを繰り返します.

は最後までクリアされず、残りの数は少数であった.

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

int n = 1000; // 2부터 1000까지의 모든 수에 대해서 소수 판별
vector<bool> arr(n + 1, true); // 처음엔 모든 수가 소수인 것으로 초기화 (0과 1은 제외)

int main(){
    // 2부터 n의 제곱근까지 모든 수를 확인하며
    for (int i = 2; i <= (int)sqrt(n); i++) {
        if (arr[i] == true) { // i가 소수인 경우 (남은 수인 경우)
            // i를 제외한 i의 모든 배수 지우기
            int j = 2; 
            while (i * j <= n) {
                arr[i * j] = false;
                j++; 
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (arr[i]) cout << i << " ";
    }

    return 0;
}

このアルゴリズムの時間的複雑度はO(Nlogn)であり,実際には非常に速く,線形時間に近く,複数の素数を探す必要がある問題に有効に利用できる.
ただし、自然数あたりの記憶が必要なのは少数であるため、大量のメモリが必要となる.たとえば、10億以下のすべての自然数を少数に判別する場合は、メモリの面で非常に非効率になる可能性があります.この点に注意して使いましょう.

関連する標準的な問題

2501号：薬をもらう

https://www.acmicpc.net/problem/2501

の2つの自然数NおよびKが与えられると、Nの約数のうちK番目の小数が出力される.

Nは1または10000未満、Kは1または1または

未満である

Nの約数がK個より少ないのでK個の約数が存在しない場合、出力0は

となる.

#include<iostream>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;

	int cnt = 0; // k번째 약수를 찾기 위한 변수 
	for (int i = 1; i <= n; i++) {
		if (n % i == 0) {
			cnt++;
			if (cnt == k) {
				cout << i << "\n";
			}
		}
	}

	if (cnt < k)
		cout << "0\n";

	return 0;
}

2581号：小数

https://www.acmicpc.net/problem/2581

M以上N以下の自然水中から少数を選出し,これら少数の和の最高値を見出した.

MおよびNは10000以下の自然数であり、MはN以下である.

セグメントは、M以上N以下の自然数のうち少数でなければ、第1行に−1が出力される.

#include<iostream>
using namespace std;

bool isPrimeNumber(int x) {
    if (x < 2) 
        return false;

    // 2부터 x의 제곱근까지 모든 수를 확인하며 
    for (int i = 2; i * i <= x; i++) {
        // x가 해당 수로 나누어 떨어진다면 
        if (x % i == 0) {
            // i와 그에 대칭인 수는 모두 x의 약수이고, x는 소수가 아님.
            return false;
        }
    }

    return true;
}

int main() {
    int m, n;
    cin >> m >> n;

    int sum = 0, min = -1;
    for (int i = m; i <= n; i++) {
        if (isPrimeNumber(i)) {
            sum += i;
            if (min == -1) // not updated
                min = i;
        }
    }

    if (sum == 0)
        cout << "-1";
    else {
        cout << sum << "\n" << min;
    }

    return 0;
}