素数求解（100~200）

短命女 2022-06-02 10:09 207阅读 0赞

**素数**又称质数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。

**方法1**：设100~200间的这个数是i，用i去分别除以2~(i-1)间的每一个数。

#include<stdio.h>
    #include<stdlib.h>
    int main()//定义类型，整型
    {
    int i, j;
    for (i = 100; i <= 200; i++)
    {
    for (j = 2; j <= i - 1; j++)
    {
    if (i%j ==0)//用i去除2~（i-1）的数
    break;//如果被整除，直接跳出循环，它不是素数
    }
    if (j == i)//如果不被整除，则输出i
    printf("%d\  ", i);//打印结果用空格或者\n隔开，以免混淆看不清最终结果
    }
    printf("\n");//将所有是素数的数打印出来
    system("pause");
    return 0;
    }

运用这种方法编程，代码过于繁琐，系统执行很慢，所以需对其进行优化

**方法2**：因为i不可能整除比i/2更大的数，所以我们可以设置第3个变量t，用来存储i/2的值。

#include<stdio.h>
    #include<stdlib.h>
    int main()
    {
    int i, j,t;//引入一个新变量t
    for (i = 100; i <= 200; i++)
    {
    t = i / 2;//由于i不可能整除比i/2更大的数
    for (j = 2; j <= t; j++)
    {
    if (i%j == 0)//用i去除小于i/2的数
    break;//如果能被整除，直接跳出循环
    }
    if (j>t)//如果不能被整除，则按大从小到大的顺序输出
    printf("%d\n", i);
    }
    printf("\n");//打印所有素数
    system("pause");
    return 0; 
    }

**方法3**：相比于i/2，用t来储存i的平方根会更优化。这种算法需要引入新的头函数math.h，和新的函数sqrt()开方函数。

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    int main()
    {
    int i, j,t;//引入一个新变量t
    for (i = 100; i <= 200; i++)
    {
    t = sqrt(i);//开方函数
    for (j = 2; j <= t; j++)
    {
    if (i%j == 0)
    break;//如果能被整除，直接跳出循环
    }
    if (j>t)//如果不能被整除，则按大从小到大的顺序输出
    printf("%d\n", i);
    }
    printf("\n");//打印所有素数
    system("pause");
    return 0; 
    }
    
    到这一步我们只是优化了内循环过程，我们还可以对外循环进行优化。

方法4：我们都知道100~200之间的偶数不可能是素数，因此我们可以人为的令i初始化为101，并每次循环时令其+2。

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    int main()
    {
    int i, j,t;//引入一个新变量t
    for (i = 101; i <= 200; i+=2)
    {
    t = sqrt(i);//开方函数
    for (j = 2; j <= t; j++)
    {
    if (i%j == 0)
    break;//如果能被整除，直接跳出循环
    }
    if (j>t)//如果不能被整除，则按大从小到大的顺序输出
    printf("%d\n", i);
    }
    printf("\n");//打印所有素数
    system("pause");
    return 0; 
    }

将减少很多运算，提高运算效率

这四种方法都可求出100——200的素数。

![SouthEast][]

[SouthEast]: /images/20220602/5741d7ebc8d04c73abbac1cc1977377a.png