素数算法-试除法和筛选法的不同境界与C语言实现

试除法

假设验证自然数n是不是质数。
1.可以验证n是否能被2~n-2整除，能整除的话则是合数，否则是质数
2.一个数如果可以因数分解的话，那么两个因数一个大于等于sqrt(n)一个小于等于sqrt(n)，如果在sqrt(n)的范围内找不到一个整数整除n，那么在大于sqrt(n)到n的范围内也找不到一个整数可以整除n。所以只需要求解验证2~sqrt(n)以内的数是否可以整除n。
3.因为除2以外所有的质数都是奇数，所以不需要验证偶数，只需要验证3~sqrt(n)的之间的奇数就可以。
4.继续总结，比如不能被3整除，则肯定不能被9整除，所以只需要除小于sqrt(n)的素数即可。

筛法

首先，2是公认最小的质数，所以，先把所有2的倍数去掉；然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；然后把所有3的倍数都去掉，剩下的那些大于3的数里面，最小的是5，所以5也是质数……
　　上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。

结果分析

对于比较大数量级的素数求解，试除法最慢，如果把试除法的验证被3~sqrt(n)奇数整除，改成验证能否被素数整除，则可以明显看到速度的提升。
效率最高的方法是筛法，与试除法对比，有大幅度的速度提升。

#include <iostream>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
//#define   max 10000
int testexcept(int max,int *prime);
int shai(int max,int*prime);
int testexcepts(int max,int *prime);
int main()
{
   
	int max, printnum=0; int option;
	double time=0.0, begin=0.0, end=0.0;
	FILE *fp;//文件指针
	fp = fopen("result.txt", "w");
	printf("请输入自然数范围\n");
	scanf_s("%d",&max);
	int* prime = new int[int(max / log(max) * 1.15) + 1];//分配数组空间
	printf("请输入求解方法1：试除法，2：筛法，3：试除素数\n");
	scanf_s("%d", &option);//方法选择

	
	
	if (option == 1) {
		begin = clock();
		printnum = testexcept(max,prime);
		end = clock();
		
	}
	else if (option == 2) {
		begin = clock();
		printnum = shai(max,prime);
		end = clock();
		
	}
	else if (option == 3) {
		begin = clock();
		printnum = testexcepts(max,prime);
		end = clock();
	}
	
	else
		printf("请重新选择，选项不正确");
	time = end - begin;
	printf("%d以内素数个数:%d。执行时间：%f\n", max, printnum, time);
	fprintf(fp, "%d以内素数个数:%d。执行时间：%f\n",max, printnum,time);
	printf("\n");
	fprintf(fp, "\n");
	printf("结果输出到文件：\n");
	fprintf(fp,"结果如下：\n");
	printf("\n");
	fprintf(fp, "\n");
	for (int i = 0; i < printnum; i++) {
		//printf("%d\t", prime[i]);
		fprintf(fp, "%d\t", prime[i]);
		if ((i + 1) % 10 == 0) {
			//printf("\n");
			fprintf(fp, "\n");
		}
			
	}
	
	fclose(fp);

	return 0;
	
}
int testexcept(int max,int *prime) {//试除法  如何修改，可以让其除素数呢？
	int i, j, k = 0, num = 0;
	for (i = 2; i <= max; i++)
	{
		if (i == 2) {
			
			
			prime[num++]=i;
			continue;
		}
		
		else if (i % 2 != 0) {
			for (j = 3; j <= sqrt(i); j += 2)
				if (i % j == 0)

					break;
			if (j > sqrt(i))
			{
				
				prime[num++]=i;
				
			}

		}


	}
	return num;
	
}
int testexcepts(int max,int *prime) {//试除素数
	int i, j, k = 0, printnum = 0, num=0;
	//int* scope = new int[int (max/log(max)*1.15) + 1];//为素数数组分配空间
	/*for (i = 0; i<int(max / log(max) * 1.15); i++) {
		scope[i] = 0;
	}//初始化*/
	//int* scope = new int[max+1];
	for (i = 2; i <= sqrt(max); i++)//求解sqrt(max)范围内的质数
	{
		if (i == 2) {
            
			prime[num++] = i;
			continue;
		}

		else if (i % 2 != 0) {
			for (j = 3; j <= sqrt(i); j += 2)
				if (i % j == 0)

					break;
			if (j > sqrt(i)){
				
				prime[num++] = i;
			}

		}

	}
	/*for (k = 0; k < num; k++) {
		printf("%d\t", scope[k]);
	}*/
	for (i = int(sqrt(max)+1); i <= max; i++) {
		for (j = 0; prime[j] <= int(sqrt(i)); j++) {
			if (i % prime[j] == 0)

				break;
			
		}
		if (prime[j] > sqrt(i)) {

			prime[num++] = i;
		}
	}
	/*for (k = 0; k < num; k++) {
		printf("%d\t", prime[k]);
	}*/
	return num;
}
int shai(int max,int *prime) {//筛法

	int* data = new int[max + 1];//分配数组空间
	int num = 0;
	for (int i = 2; i <= max; i++) {
		data[i] = 1;
	}//初值
	for (int i = 2; i <= max; i++) {
		if (data[i] == 1){
			prime[num++] = i;
			
			for (int j = 2 * i; j <= max; j = j + i) {
				data[j] = 0;
			}
		}
		

	}
		return num;
}