-
C#教程之C# 4.0 大数的运算--BigInteger的应用详解
前段时间,有个同事说
“30000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000001”
是个质数。
直觉告诉我,光是在中间加几个0,在后面加个1,估计不是质数。
有很多面试题,都会要面试者去做一些关于大数的运算,例如在这里就有判断上面这个数是不是质数的情况。
很明显,Integer ,Long都是不能来处理如此巨大的数的。
在.net framework 4.0中,System.Numerics.dll 中提供了BigInteger 类。使用这个类可以很方便的解决这个问题。
判断n是质数的方法:
1:如果是偶数,肯定不是质数
2:如果能够被小于或等于Sqrt(n) 的数除尽,则不是质数。
代码如下:
private static bool IsPrime()
{
string largeNumber = @"30000000000000000000000...000000001”;
BigInteger bigInteger = BigInteger.Parse(largeNumber);
if (bigInteger.IsEven)
{
return false;
}
for (BigInteger bi = 3; BigInteger.Pow(bi, 2) <= bigInteger; bi += 2)
{
if (bigInteger % bi == 0)
{
return false;
}
}
return true;
}
本来for 循环中的代码应该是
for (BigInteger bi = 3; bi <= BigInteger.Sqrt(bigInteger); bi += 2)
{
if (bigInteger % bi == 0)
{
return false;
}
}
可惜的是BigInteger 不支持Sqrt方法,所以换用
for (BigInteger bi = 3; BigInteger.Pow(bi, 2) <= bigInteger; bi += 2)
结果如下图:
可以知道”30000000000000000000000000…………………………..1”不是质数,可以被13除尽。
2:C语言中有道经典的题目是求100!后面有几个0.
如果你不知道BigInteger的话,应该怎么做?
100! 可以理解为
因为偶数比5要多,所以i值比j值多很多,所以求100!有多少个0,可以认为是求j的值
当然也可以用公式
Sum = [100/5]+[100/(5^2)]+[100/(5^3)]=20+4+0=24;
如果你既没有思路,也没有公式,脑子里面只有一个念头:1*2*3*4*5*..*100 的for循环,然后统计0的数量的话,在4.0 中也可以实现,虽然好像速度慢了点,不过也还是可以得到答案的:
代码如下:
统计的代码如下:
运行结果如下:
int count = 0;
for (int i = strSum.Length - 1; i >= 0; i--)
{
if (strSum[i] == '0')
{
count++;
}
else
{
break;
}
}
还有很多使用大数的运算的地方,都等待着你的发挥!
“30000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000001”
是个质数。
直觉告诉我,光是在中间加几个0,在后面加个1,估计不是质数。
有很多面试题,都会要面试者去做一些关于大数的运算,例如在这里就有判断上面这个数是不是质数的情况。
很明显,Integer ,Long都是不能来处理如此巨大的数的。
在.net framework 4.0中,System.Numerics.dll 中提供了BigInteger 类。使用这个类可以很方便的解决这个问题。
判断n是质数的方法:
1:如果是偶数,肯定不是质数
2:如果能够被小于或等于Sqrt(n) 的数除尽,则不是质数。
代码如下:
复制代码 代码如下:
private static bool IsPrime()
{
string largeNumber = @"30000000000000000000000...000000001”;
BigInteger bigInteger = BigInteger.Parse(largeNumber);
if (bigInteger.IsEven)
{
return false;
}
for (BigInteger bi = 3; BigInteger.Pow(bi, 2) <= bigInteger; bi += 2)
{
if (bigInteger % bi == 0)
{
return false;
}
}
return true;
}
本来for 循环中的代码应该是
复制代码 代码如下:
for (BigInteger bi = 3; bi <= BigInteger.Sqrt(bigInteger); bi += 2)
{
if (bigInteger % bi == 0)
{
return false;
}
}
可惜的是BigInteger 不支持Sqrt方法,所以换用
for (BigInteger bi = 3; BigInteger.Pow(bi, 2) <= bigInteger; bi += 2)
结果如下图:
可以知道”30000000000000000000000000…………………………..1”不是质数,可以被13除尽。
2:C语言中有道经典的题目是求100!后面有几个0.
如果你不知道BigInteger的话,应该怎么做?
100! 可以理解为
因为偶数比5要多,所以i值比j值多很多,所以求100!有多少个0,可以认为是求j的值
当然也可以用公式
Sum = [100/5]+[100/(5^2)]+[100/(5^3)]=20+4+0=24;
如果你既没有思路,也没有公式,脑子里面只有一个念头:1*2*3*4*5*..*100 的for循环,然后统计0的数量的话,在4.0 中也可以实现,虽然好像速度慢了点,不过也还是可以得到答案的:
代码如下:
统计的代码如下:
运行结果如下:
复制代码 代码如下:
int count = 0;
for (int i = strSum.Length - 1; i >= 0; i--)
{
if (strSum[i] == '0')
{
count++;
}
else
{
break;
}
}
还有很多使用大数的运算的地方,都等待着你的发挥!
栏目列表
最新更新
nodejs爬虫
Python正则表达式完全指南
爬取豆瓣Top250图书数据
shp 地图文件批量添加字段
爬虫小试牛刀(爬取学校通知公告)
【python基础】函数-初识函数
【python基础】函数-返回值
HTTP请求:requests模块基础使用必知必会
Python初学者友好丨详解参数传递类型
如何有效管理爬虫流量?
SQL SERVER中递归
2个场景实例讲解GaussDB(DWS)基表统计信息估
常用的 SQL Server 关键字及其含义
动手分析SQL Server中的事务中使用的锁
openGauss内核分析:SQL by pass & 经典执行
一招教你如何高效批量导入与更新数据
天天写SQL,这些神奇的特性你知道吗?
openGauss内核分析:执行计划生成
[IM002]Navicat ODBC驱动器管理器 未发现数据
初入Sql Server 之 存储过程的简单使用
这是目前我见过最好的跨域解决方案!
减少回流与重绘
减少回流与重绘
如何使用KrpanoToolJS在浏览器切图
performance.now() 与 Date.now() 对比
一款纯 JS 实现的轻量化图片编辑器
关于开发 VS Code 插件遇到的 workbench.scm.
前端设计模式——观察者模式
前端设计模式——中介者模式
创建型-原型模式