[算法总结] 基础课---有关素数

试除法判定素数 细节:

如果是i*i 可能会爆,如果是sqrt又会因为反复调用函数而爆时

code:

#include 
#include 

using namespace std;

bool is_prime(int x)
{
    if (x  n;

    while (n -- )
    {
        int x;
        cin >> x;
        if (is_prime(x)) puts("Yes");
        else puts("No");
    }

    return 0;
}

分解质因数(√ n ) 细节:

算术基本定理： 任何一个大于1的自然数N,如果N不为质数算术基本定理： 任何一个大于1的自然数N,如果N不为质数 那么N可以唯一分解成有限个质数的乘积N=p1a1∗p2a2…∗pnan 且最多只有一个大于√n的质因子，这里P1