外贸网站有哪些平台,河北手机网站制作哪家好,开网店需要什么条件,广州做网站的哪家好目录 什么是质数#xff08;素数#xff09;#xff1f;第一种方法#xff0c;暴力解决第二种方法#xff0c;用奇数第三种方法#xff0c;奇数双管齐下第四种方法#xff0c;巧用数组第五种方法#xff0c;巧用平方根写法1#xff1a;写法2#xff1a; 总结 什么是质… 目录 什么是质数素数第一种方法暴力解决第二种方法用奇数第三种方法奇数双管齐下第四种方法巧用数组第五种方法巧用平方根写法1写法2 总结 什么是质数素数
质数又称素数。一个大于1的自然数除了1和它自身外不能被其他自然数整除的数叫做质数否则称为合数规定1既不是质数也不是合数。———来自百度百科
第一种方法暴力解决
我们设定一个数为x根据质数的定义判断x是否为质数我们看它能否被2、3、4······、x-1整除如果它不能被其中任何一个整数整除则这个数就是质数。 比如要判断11是不是质数我们就看能否被下面这10个数整除。 2、3、4、5、6、7、8、9、10 因为11无法被其中任何一个数整除则判断它为质数。
如果我们要找1—1000内的质数我们可以控制x从2自己增到1000并且x每次自增1过后都要从2开始找能否被x所整除的数直到找不到结束。所以我们可以用两层for循环来控制第一层来控制x产生2–1000数字第二层for循环产生2到x-1的数并且判断能否被整除。因为1不是质数把1排除在外
并且我还设置了一个计数器count来统计大概运算的次数方便和下面方法做对比。代码如下 //求1--1000内的质数素数
#include stdio.h
int main()
{int x 0; int i 0;unsigned int count 0; //统计运算的次数for (x 2; x 1000; x) //在2到1000之间找质数{for (i 2; i x; i) //试除法能不能被x整除从2开始找直到等于x{count;if (x % i 0) //找到能被x整除的数了{break;}}if (x i) //找到和x相等也没有被整除的证明是质数{printf(%d ,x);}}printf(\n\n\n);printf(运算的次数%d ,count);return 0;
}第一种方法运行结果
第二种方法用奇数
第一种方法是否有点复杂呢这是当然的。 其实我们从质数 2、3、5、7、9、11、13、17、19······中发现什么规律了没有呢
嘿嘿嘿那就是除了2以外那些2的倍数4、6、8、10、12、14、18·······都不是质数。
所以我们的第一层for循环是不是可以不用一步步自增1而是从3开始自增2呢从而产生3、5、7、9、11······这样就把偶数给巧妙避免了。代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
int main()
{int x 0;int i 0;unsigned int count 0;x 2;printf(%d ,x); //已经知道2为质数所以先第一个打印for (x 3; x 1000; x 2) //从3开始自增2{for (i 2; i x; i){count;if (x % i 0){break;}}if (x i){printf(%d ,x);}}printf(\n\n\n);printf(运算的次数%d , count);return 0;
}第二种方法运行结果 第一种和第二种对比图片 大家发现了没有好像第二种并没有比第一种运算要少很多这个是因为当判断33、66、666这些在开始阶段i3的时候马上就可以判定不是质数了所以运算次数并没有怎么减少。
第三种方法奇数双管齐下
结合第二种方法除了2以外那些2的倍数4、6、8、10、12、14、18·······都不是质数。 所以除了2以外质数一定是奇数。 从而判断11是否为质数的时候我们不再需要判断能否被2、3、4、5、6、7、8、9、10这9个数整除我们只需要判断 能否被3、5、7、9这几个数整除即可。 所以我们可以控制第二层for循环不再自增1而是从3开始自增2。 代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
int main()
{int x 0;int i 0;unsigned int count 0;x 2;printf(%d ,x);for (x 3; x 1000; x 2) //只产生奇数{for (i 3; i x; i 2) //只产生奇数{count;if (x % i 0){break;}}if (x i){printf(%d ,x);}}printf(\n\n\n);printf(运算的次数%d , count);return 0;
}第三种方法运行结果
第四种方法巧用数组
在第三种的基础上再看我们还发现如下规律 不能被3整除的整数也无法被大于3的那些3的倍数6、9、12······整除。 不能被5整除的整数也无法被大于5的那些倍数10、15、20······整除。 所以如果整数x无法被小于x的质数整除那么x就是质数。 根据这个条件我们求质数就有了另外一条思路我们用数组来保存质数控制x自增后用x除去数组的每一个元素如果不能整除则是质数并且保存到数组中。
因此我们先把2、3这两个质数保存到数组中第一层for循环依旧是控制x自增第二层for循环来遍历数组。遍历后如果都不能整除则存到数组中。如果有一个能被整除则不是质数不保存。
代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
int main()
{int arr[500] { 0 };int x 0;int i 0;unsigned int count 0;int sum 0; //定义数组的下标arr[sum] 2; //把2存到数组中sum;arr[sum] 3; //把3存到数组中sum;for (x 5; x 1000; x 2){//从下标0开始遍历直到数组的最后一个质数for (i 0; i sum; i ) {count;if (x % arr[i] 0){break;}}if (sum i) //遍历后都不能整除{arr[sum] x; //把质数保存到数组中sum; //下标加1为下次放做准备}}for (i 0; i sum; i){printf(%d , arr[i]);}printf(\n\n\n);printf(运算的次数%d , count);return 0;
}运算结果
第五种方法巧用平方根
写法1
我们设两个整数a和b如果不是质数的话整数x就可以写成 xa * b 比如 362 * 18 363 * 12 364 * 9 366 * 6 如果整数x为质数那么就不可能写成 x a * b的形式。所以如果整数x无法被小于等于x的平方根的质数整除则x为质数。 因此我们可以在第四种方法上改造一下就是在第二层for循环从数组的第一个元素出发每一个都写成平方直到平方大于整数x退出循环。 代码如下
//第五种方法巧用平方根,写法1
#include stdio.h
int main()
{int arr[500] { 0 };int x 0; //定义要找质数的变量int i 0;unsigned int count 0;int sum 0; //定义数组下标arr[sum] 2; //2是质数储放到数组中sum;arr[sum] 3; //3也是质数放到数组中sum;for (x 5; x 1000; x 2) //只查找奇数{for (i 0;arr[i] * arr[i] x; i) //利用数组中的元素平方去排查{count;if (x % arr[i] 0) //不是质数{break;}}if (arr[i]*arr[i]x) //为质数{arr[sum] x; //把找到的奇数放到数组中sum; //下标加1}}for (i 0; i sum; i){printf(%d ,arr[i]);}printf(\n\n\n);printf(运算的次数%d , count);return 0;
}运算结果
写法2
我们不要数组也可以直接在第三种方法上改造。 代码如下
//第五种方法巧用平方根,写法二
#include stdio.h
int main()
{int x 0;int i 0;unsigned int count 0;x 2;printf(%d ,x);for (x 3; x 1000; x 2){for (i 2; i*ix; i) //控制第二层循环{count;if (x % i 0){break;}}if (i*ix){printf(%d ,x);}}printf(\n\n\n);printf(运算的次数为%d ,count);return 0;
}运算结果
总结
我们从第一种的简单粗暴到最后的优良改造运算次数一步步地减少大家是否领悟到了编程的优美了呢我特别推荐最后一种的写法二既不用数组也可以节省很多的运算时间。
如果有错误的地方还有改进的方法欢迎在评论区指出。 既然都看到这里了点个赞呗嘿嘿嘿。
