质数

质数的定义：若一个正整数无法被1和他自身除外的任意自然数整除，则称该数为质数，否则为合数。

0和1不是质数也不是合数
质数的数量：在整个自然数集合中，质数的数量不多，分布比较稀疏，对于一个足够大的整数N，不超过N的质数大约个每个数中大约有一个质数。

试除法

试除法用于解决质数的判定给出一个数n，判定n是不是质数。
定理：若一个正整数N为合数则存在一个能整除N的数T，其中。
证明：因为N是合数，所以一定存在一个数M能整除N，并且。
反证法，假设上面命题不成立，不存在这样的M，那么M一定。因为M能整除N所以N/M也能整除N，并且，令存在这样数使得假设不成立，原命题成立。
我们只需要扫描2~直接的所有整数，依次检查他们能否整除N，如果都不能N是质数，否则N是合数。

bool get_prime(int n){
    if(n<=1)return false;
    for(int i = 2;i<=n/i;i++){
        if(n%i==0)return false;
    }
    return true;
}