山野莽夫

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

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

2019年10月7日 3383点热度 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来减少垃圾评论。了解我们如何处理您的评论数据。

    联系方式

    QQ群 | TG群 | 邮箱

    最新 热点 随机
    最新 热点 随机
    Azure Student 微软云 学生订阅 免费12个月用量避坑注意点集合 MP3音频文件格式详细解析 python按固定采样点个数分割wav格式音频 愉快使用谷歌免费人工智能平台colab,训练你的神经网络模型,为你的学术生活添砖加瓦 华为云版轻量应用服务器-云耀云服务器简单体验评测 Cloudflare 免费CDN自定义节点ip之自选cloudflare 高速节点ip工具分享
    计算方法实习----改进平方根法 百家号的莫名其妙之看不懂的推广信息和推荐机制以及我的处理过程 大江东去小说(阿耐) wordpress大学wpdx1.3主题分享 留言板 谷歌云服务Google Cloud(GCP)不换号重新开启300美元试用并且保留老号虚拟机实例的方法
    标签聚合
    宝塔面板 c语言 onedrive wordpress ppt 地震学程序 虚拟机 模板
    最近评论
    小菜菜 发布于 6 个月前(11月24日) 这玩意已经废了,成收割工具了,不能再用了。
    eamon 发布于 7 个月前(11月07日) 我一年不用了才发现这个休眠管理费每月15,一共扣了我135元,然后我消费还消费不了,我宁愿消费掉也不...
    magic 发布于 11 个月前(07月03日) 请问账号不注销会有什么影响吗?
    magic 发布于 11 个月前(07月01日) 我想问一下 如果不注销账号就留着会怎么样
    qwp6601 发布于 12 个月前(06月04日) 有没有方法改为bing

    COPYRIGHT © 2021 shanyemangfu.com. ALL RIGHTS RESERVED.

    Theme Kratos Made By Seaton Jiang

    蜀ICP备15031791号-2