C语言素数优化方法
题目：求1~N范围中的素数。k为当前数值，j为被除数 素数：一个大于1的自然数中，除了1和本身外无法整除其余数的数值。
优化方法：
- （除数去双）对于素数，可以忽略双数部分，因为均能被2整除，2也是素数做特殊情况，直接输出，即除去双数的可能，数据减少一半，即执行效率要提高一倍，k初始化为3，k+=2。
- （被除数去双）因为k只可能为单数，所有被除数可忽略双数，被除数 j 初始化为3，每次 j += 2。
- （开根）对于判断， 因为不是质数，那么一定可以表示成两个数（除了1和它本身）相乘，这两个数必然有一个小于等于它的平方根。只要找到小于或等于的那个就行了，用当前数值从3开始至当前数值的开根范围的数求余数，运行效率再次提高。
- （判断）对于余数不等于0且 j 小于当前数值的开根值的情况，循环执行被除数 j += 2，若被除数 j 大于开根植，则当前数值为素数；对于余数==0的情况，表示不是素数。
具体实现代码：
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
void get_prime(char *s)
{
int N = atoi(s);
int j = 3;
double k = 3.0;//便于sqrt开根
int n = 1;
//2为特殊的素数
printf("%d\t",2);
//从3开始到N，依次找出素数
while((int)k < N)
{
j = 3;
//被除数小于当前数值的开根，且不能整数的情况
while( j < sqrt(k) && ((int)k % j != 0) )
{
j += 2;//k不等于双数，被除数也可忽略双数部分数值
}
//如果一直到j大于开根值都不能整除则为素数
if( j >= sqrt(k) )
{
printf("%d\t", (int)k);
n++;
if(n%5 == 0)
printf("\n");
}
k += 2;
}
printf("\n");
}
int main(int argc, char **argv)
{
printf("求1~%s的素数:\n",argv[1]);
get_prime(argv[1]);
return 0;
}PS：
atoi (表示 ascii to integer)是把字符串转换成整型数的一个函数，应用在计算机程序和办公软件中。int atoi(const char *nptr) 函数会扫描参数 nptr字符串，会跳过前面的空白字符（例如空格，tab缩进）等。如果 nptr不能转换成 int 或者 nptr为空字符串，那么将返回 0 [1] 。特别注意，该函数要求被转换的字符串是按十进制数理解的。atoi输入的字符串对应数字存在大小限制（与int类型大小有关），若其过大可能报错-1。
#include <iostream>
using namespace std;
bool prime(double m)//判断素数
{
int i = 0;
if ((int)m == 0) return 0;
if ((int)m == 1) return 0;
if ((int)m == 2) return 1;
for (i = 3; i <= sqrt(m); i += 2)
if ((int)m % i == 0) return 0;
if (i >= sqrt(m)) return 1;
else return 0;
}
int main()
{
double i = 3.0;
cout << 2 << endl;
for ((int)i ; i < 100; i+=2)
{
if (prime(i))
{
cout << i << endl;
}
}
system("pause");
return 0;
}问题
输出100以内的素数：
#include <iostream>
#include <math.h>
using namespace std;
bool prime(int m) {
int i = 0;
if (m == 0) return 0;
if (m == 1) return 0;
if (m == 2) return 1;
for (i = 3; i <= sqrt(m); i += 2)
if (m % i == 0) return 0;
if (i >= sqrt(m)&&i!=3) return 1;
else return 0;
}
int main() {
cout << 2 << endl;
for (int i = 3; i < 100; i+=2)
{
if(prime(i)) cout << i << endl;
}
system("pause");
return 0;
}输出结果：缺失了3、5、7（即3-8以内的判断）（9之前的所有数开根号都小于i=3，所以出现了问题）
2
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
请按任意键继续. . .优化：
#include <iostream>
#include <math.h>
using namespace std;
bool prime(int m) {//解决了素数判断缺失前面几个数的问题
int i = 0;
if (m>= 0 && m <= 8){
if(m==2 || m==3 || m==5 || m==7)return 1;
else return 0;
}
for (i = 3; i <= sqrt(m); i += 2)
if (m % i == 0) return 0;
if (i >= sqrt(m)) return 1;
else return 0;
}
int main() {
cout << 2 << endl;
for (int i = 3; i < 100; i+=2)
{
if(prime(i)) cout << i << endl;
}
system("pause");
return 0;
}输出结果：
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
请按任意键继续. . .素数：又称质数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。
如果要找出N以内的所有素数，大家都是这样想的：
#include <stdio.h>
#define N 100
int main()
{
int i,j;
for(i = 2;i <= N;i++)
{
for(j = 2;j < i;j++)
{
if(i % j == 0)
{
break; //找到因数，退出最里面的循环
}
}
if(j == i) //判断因素是不是自己本身
{
printf("%d ",i);
}
}
return 0;
}像上面这样一个一个数的找过去，再查找因数，如果N是一个本大的数的话，这个耗时将是不可想像的，所以要对以上的算法进行优化一下。
1、缩小查找因素的范围
也就是缩小自变量是 j 的 for 循环，在查找因数的其实可以查找到（平方根+1）就可以了（+1是为了判断有没有整数的平方根，如果没有 j 就会运行到平方根+1，如果有，就会运行j 就会运行到平方根），所以现在可以把 j 的值局限到（平方根+1）：
#include <stdio.h>
#include <math.h>
#define N 100
int main()
{
int i,j;
for(i = 2;i <= N;i++)
{
for(j = 2;j < (int)sqrt(i) + 1;j++)
{
if(i % j == 0)
{
break; //找到因数，退出最里面的循环
}
}
if(j == (int)sqrt(i) + 1) //判断因素是不是自己本身
{
printf("%d ",i);
}
}
return 0;
}相对于一开始的那个方法，这个可以缩短了一段时间，不过当N足够大的时候，这个方法还是不可行的。
2、用数组标记素数
可以先创建一个大小是N + 1的数组，如果是素数就标记对应的值为0，不是素数对应的值就标记为1，等所有数据都判断完了再输出数组中的数据；
#include <stdio.h>
#include <math.h>
#define N 10000
int main()
{
int i,j;
int number[N + 1] = {0}; //是素数就保持为0，是合数就赋值为1
for(i = 2;i <= (int)sqrt(N);i++)
{
if(number[i] == 0) //素数
{
for(j = i * i;j <= N;j += i) //所有i的倍数都不是素数
{
number[j] = 1;
}
}
}
for(i = 2;i <= N;i++)
{
if(number[i] == 0)
{
printf("%d ",i);
}
}
return 0;
}题目一：
请实现一个函数，对于给定的整型参数N，依次打印出小于N的素数。
解法一：试除法
由素数的定义我们很自然的会想到如下代码：
#include <stdio.h>
void print_prime(int n)
{
int i=0;
for(i=2;i<=n;i++)
{
int j=0;
for(j=2;j<i;j++)
{
if(0==i%j)
break;
}
if(j==i)
printf("%d\t",i);
}
}
int main()
{
int num=0;
scanf("%d",&num);
print_prime(num);
return 0;
}在上面的代码中，我们看到在判断素数时一直从2试除到n－1。这里从n／2之后的数到n－1的试除显然是多余的，比如某个数不能被3整除，必然不能被6整除。
优化1:
试除的范围优化到［2，n／2］，这样一下子就将工作量减少了一半，代码如下：
void print_prime(int n)
{
int i=0;
for(i=2;i<=n;i++)
{
int j=0;
for(j=2;j<=i/2;j++) //修改部分
{
if(0==i%j)
break;
}
if(j==(i/2+1)) //修改部分
printf("%d\t",i);
}
}既然能将试除范围优化到［2，n/2］，那么这个范围是不是还能优化呢？答案是可以的，在［2，n/2］这个范围里（√n，n／2］的试除也是多余的。因为因数是成对出现的，比如16可分解为：1和16 、2和8、4和4、8和2、16和1。这些因数里必然有一个小于等于4。所以只需试除小于等于√n的数就可以了。
优化2:
试除范围优化为［2，√n］，代码如下：
#include <stdio.h>
#include <math.h>
void print_prime(int n)
{
int i = 0;
for (i = 2; i <= n; i++)
{
int j = 0;
for (j = 2; j <= sqrt(i); j++) //修改部分
{
if (0 == i%j)
break;
}
if (j >sqrt(i)) //修改部分
printf("%d\t", i);
}
}
int main()
{
int num = 0;
scanf("%d", &num);
print_prime(num);
return 0;
}上面所有的代码在找素数的时候是从2到n，在这个范围内除了2之外的偶数都不是素数，所以我们可以跳过这些偶数。
还有试除范围内除了2之外的偶数也是没有必要的，因为如果不能被2整除，必然不能被大于2的偶数整除。
优化3：
寻找素数时跳过偶数、试除范围跳过除2之外的偶数。代码如下：
void print_prime(int n)
{
int i = 0;
if (n >= 2) //修改部分
printf("%d\t", 2);
for (i = 3; i <= n; i+=2) //修改部分
{
int j = 2;
if(0==i%j) //修改部分
break;
for (j = 3; j <= sqrt(i); j+=2) //修改部分
{
if (0 == i%j)
break;
}
if (j >sqrt(i))
printf("%d\t", i);
}
}其实在上面的代码中，试除范围内的一些数也是不必要的。比如判断101是否为素数时，要分别试除小于10的2和所有奇数，即2、3、5、7、9，其实对9的试除是不必要的。即对所有的非素数的试除是不必要的，因为非素数必然可分解为比它小的素数的乘积，既然它的质因数不能整除某个数，这个数必然也不能。故试除的范围可缩小到小于等于√n的所有素数。
优化4:
只试小于√n的素数
那么问题来了，要试除这些素数时必然要将前面求出的素数保存起来，开辟多大一块空间合适呢？因为n的大小未知，所以无法确定开辟多少空间。这里可以使用动态内存开辟空间，当空间不够时使用realloc()追加空间。
代码实现如下：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define LEN 10 //每次开辟空间的大小
void print_prime(int n)
{
int *p = (int*)calloc(sizeof(int),LEN);
if (p == NULL)
{
printf("out of memory !\n");
exit(EXIT_FAILURE);
}
int i = 0, j = 1;
int count = 1;
if (n >= 2) //第一个素数，输出并保存起来
{
printf("%d\t", 2);
p[0] = 2;
}
for (i = 3; i <= n; i += 2)
{
int k = 0;
while (p[k]>0 && p[k] <= sqrt(i)) //试除保存的素数
{
if (i%p[k] == 0)
break;
k++;
}
if (!p[k] || (p[k] > sqrt(i))) //将新求出的素数保存起来
{
printf("%d\t", i);
if (j >= (LEN*count))
{
count++;
p = realloc(p, sizeof(int)*LEN*count);
if(p==NULL)
exit(EXIT_FAILURE);
}
p[j] = i;
j++;
}
}
free(p);
}
int main()
{
int num = 0;
scanf("%d", &num);
print_prime(num);
return 0;
}解法二：筛法
这种方法求素数的思想就是，不断筛去最小的数的倍数。这个最小的数必然是素数。
比如最小的素数是2，去掉所有2的倍数；接下来最小的数是3，3就是素数，去掉所有的3的倍数；依次类推，直到最小的数小于等于√n为止。为什么是√n呢？ 在上面的试除法中讲到只要试除小于等于√n的所有素数即可判断出小于等于n的所有素数，这里同样适用，只要去掉所有的小于等于√n的所有数的倍数，剩下的数就是小于等于n的所有素数。
代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void print_prime(int n)
{
int *arr=(int*)malloc(sizeof(int)*n);
if (arr == NULL)
{
printf("out of memory !\n");
exit(EXIT_FAILURE);
}
int i = 0, j = 0;
for (i = 0; i < n - 1; i++) //初始化数组［2，n］
{
arr[i] = i + 2;
}
while (arr[j] <= sqrt(n)) //除数的范围
{
for (i = j + 1; i < n - 1; i++)
{
if (arr[i] % arr[j] == 0)//筛去arr[i]的倍数
arr[i] = 0;
}
j++;
while (!arr[j]) //确定最小数
j++;
}
for (i = 0; i < n - 1; i++) //打印素数
{
if (arr[i])
printf("%d\t", arr[i]);
}
free(arr);
}
int main()
{
int num = 0;
scanf("%d", &num);
print_prime(num);
return 0;
}上面的代码有一个很明显的缺陷就是开辟的空间过大，如何来解决这个问题呢？
上面代码所开辟的空间为int型，占用空间太多，我们可以构造一个bool型数组，以下标来存储数据，这样就节省了75%的空间。
优化1：
构造bool型数组，以下标来存储数据,每个数只占一个字节。
代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
void print_prime(int n)
{
bool *arr=(bool*)malloc(sizeof(bool)*n);
if (arr == NULL)
{
printf("out of memory !");
exit(EXIT_FAILURE);
}
int i = 0, j = 2;
for (i = 0; i <= n; i++)//初始化数组为true
{
arr[i] = true;
}
while (j <= sqrt(n)) //除数的范围
{
for (i = j + 1; i <= n; i++)
{
if (i%j == 0)
arr[i] = false; //筛除
}
j++;
while (!arr[j]) //寻找最小数
j++;
}
for (i = 2; i <= n; i++) //打印素数
{
if (arr[i])
printf("%d\t", i);
}
free(arr);
}
int main()
{
int num = 0;
scanf("%d", &num);
print_prime(num);
return 0;
}上面的代码使用bool类型占一字节来存储数据，想到这里，我们是不是可以用位来存储数据，一个字节有8位，每位节用bool值来表示这样空间利用率会大大的提高。
优化2:
构造定长的byte数组，用bit位存储数据
代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//将ch的第position位 置0
unsigned char set_bit_0(unsigned char ch, int position)
{
return ch & (~ ( (unsigned char)pow(2, position) ) );
}
//找arr指向的内存第position个位起，第一个不为0的比特位
int check_bit_1(int num,const unsigned char *arr, int pos)
{
while (pos<= num)
{
if (( (arr[pos / 8] >> (pos % 8) ) & 1) == 1)
return pos;
pos++;
}
return 0;
}
//求解素数
void print_prime(int n)
{
unsigned char *arr = (unsigned char*)malloc(sizeof(unsigned char)*n / 8+1);
if (arr == NULL)
{
printf("out of memory !\n");
exit(EXIT_FAILURE);
}
int i = 0,j=2;
for (i = 0; i < n/8+1; i++) //将bit数组置为全1
{
arr[i] = 0xff;
}
while (j <= sqrt(n)) //筛除范围
{
for (i = j + 1; i <= n; i++)
{
if (i%j == 0) //将非素数对应的位 置0
arr[i / 8] = set_bit_0( arr[i / 8] , i % 8);
}
j++;
j = check_bit_1(n,arr, j);
if (j == 0)
break;
}
for (i = 2; i <= n; i++) //打印素数
{
i = check_bit_1(n,arr, i);
if (i == 0)
break;
printf("%d\t", i);
}
}
int main()
{
int num = 0;
scanf("%d", &num);
print_prime(num);
return 0;
}题目二：
从小到大依次打印N个素数
解法一：试除法
经过题目一的求解优化，这里直接给出试除法优化的终极版：试除保存起来的素数。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void print_N_prime(int num)
{
int count = 0;
int i = 3,j=0,flag=2;
int *arr = calloc(num,sizeof(int));
if(arr==NULL)
{
printf("out of memory !\n");
exit(EXIT_FAILURE);
}
arr[0] = 2;
count = 1; //统计素数的个数
while (count<num)
{
for (j = 0; arr[j] <= sqrt(i) && arr[j] ; j++) //试除判断素数
{
if (i%arr[j] == 0)
break;
}
if (arr[j] > sqrt(i))
{
arr[count]=i;
count++;
}
i++;
}
for (i = 0; i < count; i++) //打印素数
{
printf("%d\t", arr[i]);
}
}
int main()
{
int n = 0;
scanf("%d", &n);
print_N_prime(n);
return 0;
}解法二：筛法
筛法需要容器，这个容器要多大呢？由素数定理可以近似求出素数的分布范围。如0～x中有x/lnx个素数，反推即可求出n个素数的分布范围，由于这只是近似，把容器再扩大30%，应该足够了。
求出范围后解法与题目一类似，只需在输出素数时控制输出个数即可。