前言
今天和大家分享一下求素数的方法。
一、筛选法求素数
题目来源：
描述
用筛选法求n以内的素数。筛选法求解过程为：将2~n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止。数组中不为0 的数即为素数。
输入描述：
多组输入，每行输入一个正整数（不大于100）。
输出描述：
针对每行输入的整数n，输出两行，第一行，输出n之内（包括n）的素数，用空格分隔，
第二行，输出数组中2之后被清0 的个数。每行输出后换行。
二、分析问题
1.常见的求素数方法（两种）
代码如下（普通）
#include<stdio.h> int main() { int i, n; printf("请输入一个数:"); scanf("%d", &n); for (i = 2; i < n ; i++) { if (n%i == 0) break; } if (n <=1 ) printf("这不是素数\n"); else if (i < n) printf("这不是素数\n"); else printf("这是素数\n"); return 0; }
因为素数是除了1和本身就没有其他整数可以作为因数的数，那么我们只要从2开始一个一个和它比对，看余数的情况就可以得出结论。但是这样一个一个比对太耗费时间了。
#include<stdio.h> #include<math.h> int main() { int n,i; double k; printf("请输入一个数："); scanf("%d", &n); k = sqrt(n); for (i = 2; i <= k;i++) { if (n%i == 0) break; } if (n <=1 ) printf("这不是素数\n"); else if (i <= k) printf("这不是素数\n"); else printf("这是素数\n"); return 0; }
其实在数学里面可以证明，我们只要用到根号n,就可以了，因为因数是对称分布的嘛，感兴趣的伙伴可以推一下。
2、本题解题过程
#include<stdio.h> #include<math.h> int main() { int n, a[100]; //初始化 for(int i = 0; i < 100; ++i) { a[i] = i + 2; } //处理为素数数组 for(int i = 2; i < 100; ++i) { for(int j = i - 1; j < 100; ++j) { if(a[j] % i == 0 && a[j] != 0) { //余数为0，不是素数，置0 a[j] = 0; } } } while (scanf("%d", &n) != EOF){ int num = 0; for(int i = 0; i < n - 1; ++i) { if(a[i] == 0) { ++num; }else{ printf("%d ", a[i]); } } printf("\n"); printf("%d\n",num); } return 0; }
总结
以上就是今天要讲的内容，本文仅仅简单介绍了求素数的几种方法，如有错误欢迎指正~
