关于判断质数只需要到n/2或到根号n的原理_质数根号 原理

        这个问题从我接触为止就成了我的心头结，现将其证明整理，感谢那些我为提供思路的同学，比如煌星。

        首先1不是质数，1原本被数学家作为质数，但是有些特殊的数可以被几个质数相乘得到的结果相同，如果1是则有多解，任何答案它都可以插一脚，所以被数学家忍痛剔除。

        质数的定义即为除1和本身外不能被其他数整除的数，带有特殊性质（质数）。

        那么判断质数只要从2到本身前进行试除，能整除即不是。这是最基本的判断。

        那么为什么只要判断到n/2呢？

        假设数为N，则N = 1*N（N是其最大因数）= 2 * (n/2)(n/2是其第二大因数) = 3 * (n/3) = 4 * (n/4)......

        且因数为正整数。

        

#define _CRT_SECURE_NO_WARNINGS 1
 
#include <stdio.h>
 
int main()
{
    int i = 0;
    int j = 0;
    for (i = 2; i <= 100; i++)
    {
        for (j = 2; j <= i / 2; j++)
        {
            if (i % j == 0)
                break;
        }
        if (j > i / 2)
        {
            printf("%d\n", i);
        }
    }
    return 0;
}

代码实现

至于根号n

注意N = p*q时，如果p是因数，则q必为因数，所以只需要判断<=根号n