山野莽夫

  • 归档
    • 随笔
    • 建站资源
    • 分享
    • 代码
  • 地球物理学
    • 专业课
    • 概念解释
  • 计算机
  • 互联网
  • 教程
  • 规划
  • 实验室
    • 珍藏的软件
    • 贴吧云签到
    • A1账号自助申请
山野莽夫
小学生的挣扎的点点滴滴
  1. 首页
  2. 代码
  3. c
  4. 正文

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

2019年10月7日 3072点热度 0人点赞 1条评论

试除法

假设验证自然数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;
}


标签: 素数
最后更新:2019年10月7日

小菜菜

菜鸟

打赏 点赞
< 上一篇
下一篇 >

文章评论

  • 婚书网

    已加入收藏夹,时不时的来看看有没有更新博文!

    2019年12月2日
    回复
  • razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
    取消回复

    此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。

    标签聚合
    宝塔面板 ppt 虚拟机 onedrive 地震学程序 c语言 模板 wordpress
    最新 热点 随机
    最新 热点 随机
    Azure Student 微软云 学生订阅 免费12个月用量避坑注意点集合 MP3音频文件格式详细解析 python按固定采样点个数分割wav格式音频 愉快使用谷歌免费人工智能平台colab,训练你的神经网络模型,为你的学术生活添砖加瓦 华为云版轻量应用服务器-云耀云服务器简单体验评测 Cloudflare 免费CDN自定义节点ip之自选cloudflare 高速节点ip工具分享
    多线程bt、http、ftp下载工具Aria2开启https模式以及面板的配置 百家号的莫名其妙之看不懂的推广信息和推荐机制以及我的处理过程 大江东去小说(阿耐) 京九高铁和鲁南高铁的交汇站-菏泽东站 Phpstudy出品免费linux小皮面板简单安装和使用评测-让天下没有难配的环境 本站提供百度贴吧自动签到工具

    COPYRIGHT © 2021 shanyemangfu.com. ALL RIGHTS RESERVED.

    Theme Kratos Made By Seaton Jiang

    蜀ICP备15031791号-2