C语言之素数判断及输出
我们要想解决素数问题首先要明确素数是什么。
文章目录
C语言之素数判断及输出 什么是素数如何计算素数素数源代码进阶：因子分解什么是素数
素数：素数一般指质数。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数（来自百度词条）。
如何计算素数
当一个数本身除了1和它本身以外不再有其他因数时为素数。
1)：因此判断一个整数num是否为素数，只需用 2 ~ num-1 （因为所有整数都能被1整除）之间的每一个整数去除num，如果都不能被整除，那么 num即一个素数。
用C语言语句表示为：
//如判断数num是否为素数flag = 0;for(int i=2;i<num;i++){if(num%i==0)flag = 1;}if{flag == 0}{//是素数 }else{//不是素数 }
这里循环可以继续做一下优化减少不必要的运算
2)：num不必被 2 ~ num-1 之间的每一个整数去除，只需被 2 ~ √num之间的每一个整数去除就可以了。如果 num不能被 2 ~ √num之间任一整数整除，num 一定是素数。
// An highlighted blockflag = 0;for(int i=2;i<=sqrt(num);i++){if(num%i==0)flag = 1;}if{flag == 0}{//是素数 }else{//不是素数 }
这里需要用到sqrt函数(求平方根),在c语言<math.h>(数学库)中直接调用即可.
素数源代码
（1）素数判断
// **判断num是否为素数**#include<stdio.h>#include<windows.h>#include <math.h>#pragma warning(disable:4996) //vs（vs）使用scanf时需要加 _s 否则会报错，用这种是解决方法之一int main(){int num, i;int flag=0; //判断标志scanf("%d", &num); //输入要判断的整数numif (num == 0){flag = 1;}for (i = 2; i <= sqrt(num); i++){if (num%i == 0){flag = 1; break;}}if (flag == 0){printf("%d是素数。\n",num);}else{printf("%d不是素数。\n", num);}system("pause"); //vs运行会直接结束运行窗口自动关闭，可以用<window.h>中的syetem函数使运行窗口保留。 return 0;}
（2）输出1~100所有的素数
// **找出1~100中所有素数**#include<stdio.h>#include<Windows.h>#include <math.h>int main(){int i = 2,flag=0;for (; i <= 100; i++){flag = 0;int j = 2;for (; j <=sqrt(i); j++){if (i % j == 0){flag++;break;}}if (flag == 0){printf("%d ", i);}}printf("是素数。\n");system("pause"); //vs运行会直接结束运行窗口自动关闭，可以用<window.h>中的system函数使运行窗口保留。 return 0;}
运行结果：
进阶：因子分解
链接：因子分解
来源：牛客网
#include <iostream>#include <cmath>using namespace std;// 求最小素因子集合void factorization(int n){cout << n << " = ";for(int i = 2; i <= sqrt(n); ++i){while(n % i == 0 && i < n){cout << i << " * ";n /= i;}}cout << n ; //这个时候最后一个因素i刚好等于n}int main(){int num;while(cin >> num){factorization(num);cout << endl;}return 0;}
代码都是自己写的，如有不对欢迎指正【抱拳】。
