米鼠商城

多快好省,买软件就上米鼠网

最新项目

人才服务

靠谱的IT人才垂直招聘平台

关于给定较大数(10亿)求质数和的 算法优化问题

  • xym01
  • 1
  • 2020-11-24 12:02

1.先给出咱们教材(C语言成绩设计基础)上的案例

#include <iostream>
#define Num 100000
using namespace std;


int main()
{
	int n=Num,k;
	for(int i=2;i<=n;i++)
	{
		for(int j=2;j<=i;j++)
		{
			if(i%j==0 && i!=j) break;
			if(i%j==0 && i==j)k=k+i;
		}
		//cout<<i<<endl;
	}
	cout<<k;

	return 0;
}

我认为这个简直不能叫做算法,这个我真不敢拿10亿来测试,所以就拿下边几组测试一下

100,000 2.442s 值:454396537
500,000 50.89s 值:1324301603
1000,000 1百万我已经不敢测试了 未测试

2.其他思路的启发

看到这个算法感觉真的很强,尤其是进行超大数计算时。

原理就是,看下边一串数字吧,从2开始 把2的倍数全去掉,然后3,把3的倍数全去掉,然后5,5的倍数去掉.....这样能把很多数给清掉

 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 .....

#include <iostream>
using namespace std;
#define Max_Num 100000

char isPrime[Max_Num+10]; //1为和数   0为质数 
int main(){
	for(int i=1;i<=Max_Num+10;i++)
		isPrime[i]=0; 
	int k=0;	
	for(int i=2;i<=Max_Num;i++)
		if(isPrime[i]==0)
		{k+=i; 
			for(int j=i*2;j<=Max_Num;j+=i)
				isPrime[j]=1;//1的就是 和数 
}
					
	//for(int i=2;i<=Max_Num;i++)
		
	//for(int i=2;i<=Max_Num;i++)
		//if(isPrime[i]==1)cout << i<<" ";
	
	//for(int i=Max_Num;true;i--)
		//if(isPrime[i]==0)
		
	//	{	cout<<i;
	//		break;	} 
	cout << k;
	
	
}

同样放出测试结果

100,000 0.03281s 值:454396537
500,000 0.04388s 值:1324301603
1,000,000 0.05515s 值:3190663655

10,000,000

0.4939s

值超出int范围

100,000,000   4.282s 值超出int范围

 

当我测试到10,000,000时,前面的质数和已经超出int的范围了,但是计算的结果 我想给大家弄出来。

于是想到一个主意,大家可以把这个超出int范围的思想拓展一下,

首先不能用定义int k;这种变量了    因为这样算出的值 超出范围,会写到下一个(int)内存当中。(有可能)造成程序崩溃,我的处理办法大家可以看一下

注意看详细的备注:

int k[20]={0,0,0,0,0,0,0,0,0,0,0,0,0};
//定义个比较长的数组  来存放这个超出一个 int 范围的值
//超出的值会写入到下一个内存地址
//因为数组的内存是连续的,所以我定义这个较长的数组来存放这个 超大数字

int *p=k;
//定义个指针  指向这个数字的首地址




//初始化数组,令其全部为0

//然后从首地址开始写出
//首地址为p

 

10,000,000 0.4939s 值:3,574,358,836‬
100,000,000 4.282s 值:‭‭‭6,851,376,204‬
1,000,000,000

47.92s

值:

Ps:做到现在,我现在也怀疑我的方法有问题,因为我用上边方法来看10亿以内的质数和的时候,写入内存的值居然比1亿还小,我目前尚且不知道问题出在哪。也请各位大佬看看我的思路是否有问题,并指点出来

 

 



这里给大家推荐一个在线软件复杂项交易平台:米鼠网 https://www.misuland.com

米鼠网自成立以来一直专注于从事软件项目人才招聘软件商城等,始终秉承“专业的服务,易用的产品”的经营理念,以“提供高品质的服务、满足客户的需求、携手共创双赢”为企业目标,为中国境内企业提供国际化、专业化、个性化、的软件项目解决方案,我司拥有一流的项目经理团队,具备过硬的软件项目设计和实施能力,为全国不同行业客户提供优质的产品和服务,得到了客户的广泛赞誉。



如有侵权请联系邮箱(service@misuland.com)

猜你喜欢

评论留言