//头文件（仅标注一次）
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>境界1：判断x是否为素数，从2一直尝试到x-1
//※试除法(针对需求1)
int main()
{
int N = 0;
int count = 0;
printf("输入N:>");
scanf("%d", &N);
printf("请输出%d以内的所有素数:>\n", N);
int i = 0;
int j = 0;
for (i = 2; i < N; i++)
{
for (j = 2; j < i; j++)
{
count++;
if (i % j == 0)
break;
}
if (j == i)
{
printf("%d ", i);
}
}
printf("\xa运算次数:>%d\n", count);
return 0;
}
境界2：所有素数都是奇数
int main()
{
int N = 0;
int count = 0;
printf("输入N:>");
scanf("%d", &N);
printf("请输出%d以内的所有素数:>\n2 ", N);
//判断素数从3开始，所以2要先写出来
int i = 0;
int j = 0;
for (i = 3; i < N; i += 2)
{
for (j = 3; j < i; j++)
{
count++;
if (i % j == 0)
break;
}
if (j == i)
{
printf("%d ", i);
}
}
printf("\xa%d\n", count);
return 0;
}
境界2.1：奇数双管齐下
除了2以外质数一定是奇数。
从而判断11是否为质数的时候，我们不再需要判断能否被2、3、4、5、6、7、8、9、10这9个数整除，
我们只需要判断 能否被3、5、7、9这几个数整除即可。
所以我们可以控制第二层for循环不再自增1，而是从3开始自增2。
int main()
{
int N = 0;
int count = 0;
printf("输入N:>");
scanf("%d", &N);
printf("请输出%d以内的所有素数:>\n2 ", N);
int i = 0;
int j = 0;
for (i = 3; i < N; i += 2)//只产生奇数
{
for (j = 3; j < i; j += 2)//只产生奇数
{
count++;
if (i % j == 0)
break;
}
if (j == i)
{
printf("%d ", i);
}
}
printf("\xa运算次数为:>%d\n", count);
return 0;
}
境界3：除了2以外，所有可能的质因数都是奇数，先尝试2，再尝试从3开始直到x/2的所有奇数
int main()
{
int N = 0;
int count = 0;
printf("输入N:>");
scanf("%d", &N);
printf("请输出%d以内的所有素数:>\n2 3 5 ", N);
int i = 0;
int j = 0;
for (i = 3; i < N; i += 2)//奇数
{//N = 100时，从2 遍历需要544次，从3遍历需要497次
for (j = 3; j < i / 2; j++)
//从3开始遍历，整体劈一半去（从3开始，不从2开始，因为2是偶数的因数，不需要遍历了）
//！！！
//但是前三个素数要自己写出来，因为开始遍历的最小素数i要 > 2 * j，即i最小是6
{
count++;
if (i % j == 0)
break;
}
if (j == i / 2)
{
printf("%d ", i);
}
}
printf("\xa运算次数:>%d\n", count);
return 0;
}
境界4：只要从 3 一直尝试到√x，就可以了。
#include<math.h>
int main()
{
int N = 0;
int count = 0;
printf("输入N:>");
scanf("%d", &N);
printf("请输出%d以内的所有素数:>\n2 3 5 7 ", N);
int i = 0;
int j = 0;
for (i = 3; i <= N; i += 2)//写11，少算一次
{//内层可以从3 开始遍历
//但是前4 个素数要自己写出来，因为开始遍历的最小素数i要 > j ^ 2
for (j = 3; j <= sqrt(i); j++)
//注意！ 这要有 ⬆ 等号
{
count++;
if (i % j == 0)
break;
}
if (j > sqrt(i))
//注意！这是＞，不能等于，等于的要被排除掉
{
printf("%d ", i);
}
}
printf("\xa运算次数:>%d\n", count);
return 0;
}
境界5：只要尝试小于√x 的质数即可（思路网上copy）
比如要判断101是否质数，101的根号取整后是10，那么，按照境界4，需要尝试的奇数分别是：3，5，7，9。
但是你发现没有，对9的尝试是多余的。不能被3整除，必然不能被9整除……
顺着这个思路走下去，这些朋友就会发现：
其实，只要尝试小于√x 的质数即可。
而这些质数，恰好前面已经算出来了（是不是觉得很妙？）。
所以，我们可以把已经算出的质数，先保存起来，然后用于后续的试除，效率就大大提高了。
顺便说一下，这就是算法理论中经常提到的： 以空间换时间。
筛选法
步骤：
1.先将1去除（1不是素数）
2.用2除它后面的各个数，把能被2整除的数去除，即把2的倍数去除掉
3.用3除后面的各个数，把能被3整除的数去除，即把3的倍数去除掉
4.分别用5、7…作为除数除这些数后面的数
这些操作需要一个很大的容器去装载所有数的集合，
只要满足这些步骤，即将大于1的且是2、3、4…的倍数全部置为0，
一直到数据集合的末尾，最终不是0的数就是素数。
#define N 100
int main()
{
int i = 0;
int j = 0;
int arr[N];//100
unsigned int count = 0;
for (i = 0; i < N; i++)
{
arr[i] = i + 1;//先赋值1~100
}
for (i = 0; i < N; i++)//主循环
{
j = i - 1;//空过0、1、2
while (j > 1)
{
count++;
if (arr[i] % j == 0)
arr[i] = 0;
j = j - 1;
}
}
for (j = 1; j < N; ++j)
{
if (arr[j] != 0)
{
printf("%d ", arr[j]);
}
}
printf("\xa运算次数:>%d\n", count);
return 0;
}
境界6：数组保存质数（感觉比5好用呢）
我们用数组来保存质数，控制x自增后，用x除去数组的每一个元素，
如果不能整除则是质数，并且保存到数组中。
//怎么和sqrt(N)联系起来呢？---不会（看境界7！！！）
#define N 100
int main()
{
int arr[N / 2] = { 2,3 };//最大开辟N/2个就足够了
int x = 0;
int j = 0;//遍历数组用
unsigned int count = 0;
int i = 2;//数组下标，从2开始
for (x = 5; x < N; x += 2)//奇数
{
//i = (arr[i] > sqrt(N)) ? i : sqrt(N);
for (j = 0; j < i; j++)
{ //arr[0]
//从数组下标0开始遍历，直到最后一个数
count++;
if (x % arr[j] == 0)
break;
}
if (j == i)//遍历后都不能整除
{
arr[i] = x;//把质数放到数组中
i++;//下标 +1
}
}
printf("请输出%d以内的所有素数:>\n", N);
for (j = 0; j < i; j++)
{
printf("%d ", arr[j]);
}
printf("\xa运算次数:>%d\12", count);
return 0;
}
境界7：平方根 + 质数数组
如果整数x为质数，那么就不可能写成 x = a * b的形式。
所以如果整数x无法被小于等于x的平方根的质数整除，则x为质数。
我们可以在第四种方法上改造一下：
就是在第二层for循环，从数组的第一个元素出发，每一个都写成平方，
直到平方大于整数x退出循环。
/*调试之后感觉境界7和境界4大差不差，而且运算次数也大差不差*/
#define N 100
int main()
{
int arr[N / 2] = { 2,3 };
int x = 0;
int j = 0;//遍历数组用
unsigned int count = 0;
int i = 2;//数组下标，从2开始
for (x = 5; x < N; x += 2)//奇数
//x = 9时，还是会用3 * 3去排除，跟境界4 感觉等价了
{//sqrt(N)不好用，就用质数的平方
for (j = 0; arr[j] * arr[j] <= x; j++)
//利用数组中元素的平方去排查
{ //arr[0]
//从数组下标0开始遍历，直到最后一个数
count++;
if (x % arr[j] == 0)
break;
}
if (arr[j] * arr[j] > x)//遍历后都不能整除
{
arr[i] = x;//把质数放到数组中
i++;//下标 +1
}
}
printf("请输出%d以内的所有素数:>\n", N);
for (j = 0; j < i; j++)
{
printf("%d ", arr[j]);
}
printf("\xa运算次数:>%d\12", count);
return 0;
}
新手入门，欢迎大家交流指正！