c语言的求素数算法,C语言求素数的算法
最后一次是出了素数的问题C语言解决题目(面试)，当时用了最粗暴的算法。回来细致參考资料，事实上答案有非常多种：
1，小学生版本号：
推断 x 是否为质数，就从 2 一直算到 x-1。
static rt_uint32_t array1[ARRAY_LEN];
void func1(void)
{
for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
{
array1[i - 1] = 0;
}
rt_uint32_t x, y = 0, z = 0;
rt_uint32_t i = 0;
for (x = 2; x <= ARRAY_LEN; x++)
{
y = 0;
for (i = 1; i <= x; i++)
{
if (x % i == 0)
{
y++;
}
}
if (y == 2)
{
z++;
array1[x - 1] = x;
}
}
array1[0] = 1;
}
2，小学生毕业版：
x 假设有质因数，肯定会小于等于 x/2。所以捏。就从 2 一直到 x/2 就可以。
static rt_uint32_t array2[ARRAY_LEN];
void func2(void)
{
for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
{
array2[i - 1] = 0;
}
rt_uint32_t x, y = 0, z = 0;
rt_uint32_t i = 0;
for (x = 3; x <= ARRAY_LEN; x++)
{
y = 0;
for (i = 2; i <= x / 2; i++)
{
if (x % i == 0)
{
y++;
break;
}
}
if (y == 0)
{
z++;
array2[x - 1] = x;
}
}
array2[0] = 1;
array2[1] = 2;
}
3，初中生版：
除了2以外的质因数都是奇数。
所以算从3開始一直到 x/2 的全部奇数。
static rt_uint32_t array3[ARRAY_LEN];
void func3(void)
{
for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
{
array3[i - 1] = 0;
}
rt_uint32_t x, y = 0, z = 0;
rt_uint32_t i = 0;
for (x = 3; x <= ARRAY_LEN; x += 2)
{
y = 0;
for (i = 2; i <= x / 2; i++)
{
if (x % i == 0)
{
y++;
break;
}
}
if (y == 0)
{
z++;
array3[x - 1] = x;
}
}
array3[0] = 1;
array3[1] = 2;
}
4，高中生版：
事实上仅仅要从 2 一直尝试到根号x。就能够了。由于x仅仅要有因数必然有一个因数小于等于根号x。
static rt_uint32_t array4[ARRAY_LEN];
void func4(void)
{
for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
{
array4[i - 1] = 0;
}
rt_uint32_t x, y = 0, z = 0;
rt_uint32_t i = 0;
for (x = 3; x <= ARRAY_LEN; x++)
{
y = 0;
for (i = 2; i <= sqrt(x); i++)
{
if (x % i == 0)
{
y++;
break;
}
}
if (y == 0)
{
z++;
array4[x - 1] = x;
}
}
array4[0] = 1;
array4[1] = 2;
}
5，本科生版：
把上面的版本号都综合起来
static rt_uint32_t array5[ARRAY_LEN];
void func5(void)
{
for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
{
array5[i - 1] = 0;
}
rt_uint32_t x, y = 0, z = 0;
rt_uint32_t i = 0;
for (x = 3; x <= ARRAY_LEN; x += 2)
{
y = 0;
for (i = 2; i <= sqrt(x); i++)
{
if (x % i == 0)
{
y++;
break;
}
}
if (y == 0)
{
z++;
array5[x - 1] = x;
}
}
array5[0] = 1;
array5[1] = 2;
}
6。本科生毕业版本号：
就是当i是质(素)数的时候，i的全部的倍数必定是合数。
假设i已经被推断不是质数了，那么再找到i后面的质数来把这个质
数的倍数筛掉。
static rt_uint32_t array6[ARRAY_LEN];
void func6(void)
{
for (rt_uint32_t i = 1; i <= ARRAY_LEN; i += 2)
{
array6[i - 1] = i;
}
for (rt_uint32_t i = 3; i < sqrt(ARRAY_LEN); i+=2)
{
if (array6[i-1])
{
for(rt_uint32_t j=i<<2;j<=ARRAY_LEN;j+=i)
{
array6[j] = 0;
}
}
}
array6[1] = 2;
}
总结
分析了6个算法在我的嵌入式平台执行结果：
定义ARRAY_LEN = 1000；
func1
2513922
func2
221563
func3
213926
func4
762945
func5
674993
func6
14663
我们能够看到func4、func5并没有我们想象的那么节省时间，我想问题主要出在sqrt上面；sqrt本身是比較耗时的计算，然后func4与func5调用sqrt的次数又比較多；所以导致结果不太乐观。
当然假设把ARRAY_LEN调大。可能结果又会不一样
至此，也就仅仅是我本科毕业的水准了，后面还有更好的纯C算法可以告诉我。
相关文章：
Python全栈Day 15部分知识点
全局变量与局部变量 约定俗成的规则：全局变量名大写，局部变量名小写。 全局变量没有缩进，顶格写。 如果函数的内容无global关键字，优先读取局部变量，能读取全局变量，无法重新赋值，但是对于可变类…
SQL执行并返回执行前/后结果
SQLServer： 1、插入数据，并返回插入的数据：INSERT INTO TestTB(Province,City) output inserted.Province, inserted.City VALUES(广东,深圳)2、同理，删除数据也是一样的，只不过是使用deleted表罢了。delete from Test…
WebStorm 运行Rect Native 项目
今天教大家如何直接使用WebStorm这个IDE直接完成编码运行项目工作.这样就可以不用打开Xcode了. 1.首先点击WebStorm右上方的下拉箭头弹出的Edit Configurations.... 2.然后会进入一个配置页面.点击左上方的.在弹出的列表中选中npm.如图. 3.在右边的配置框中,先选择Command为hel…
Win7下用VS2010编译QGIS2.9.0
折腾了两天了，终于吧QGIS2.9.0在VS2010下面编译过了。 参考了许多的博客，在网络环境极为和（e）谐（lie）的情况下用Google查了好多资料。 其实原创的东西真的不多，但是毕竟是自己亲身实践得到的成…
软件工程第二次课后作业——Gaoooo
代码量：9行 码云仓库：https://gitee.com/Gaooo/2016035107059.git 实现时间：emmmmm（9行代码，自己估计！！） 程序对表达式类型的支持程度：全部支持！ 能支持两个操…
android检测本地是否安装,在本地测试模块的安装
Play 核心库可让您在本地测试应用是否能够执行以下操作，而无需连接到 Play 商店：请求并监控模块的安装。处理安装错误。本页介绍了如何将应用的拆分 APK 部署到测试设备，以便 Play 核心自动使用这些 APK 模拟从 Play 商店请求、下载和安装模块…
IsPostBack的使用
protected void Page_Load(object sender, EventArgs e){//当前用户通过Index.aspx页面中“添加用户”链接跳转到该页面时，这是一次get请求，所以不会提交表单，拿不到隐藏域的值。当前页面显示完成，用户在表单中输入数据以后单击提…
WebStorm下ReactNative代码提示设置
ReactNative 代码智能提醒 (Webstrom live template) https://github.com/virtoolswebplayer/ReactNative-LiveTemplate ReactNative的代码模板,包括: 1.组件名称 2.Api 名称 3.所有StyleSheets属性 4.React组件 安装 方法一 file -> import settings -> ReactNative.ja…
WinXp安装Oracle 11g Express Edition
由于在虚拟机上学习（怕把真机器搞坏了），这次是在Windows XP上安装Oracle 11g Express。 本文安装的是Oracle 11g Express，是Oracle数据库的快速版（学习版），安装包大小只有几百MB。 到Oracle的…
html语言书写注意事项,CSS命名规范参考及书写注意事项
CSS书写顺序*{/*显示属性*/displaypositionfloatclearcursor…/*盒模型*/marginpaddingwidthheight/*排版*/vertical-alignwhite-spacetext-decorationtext-align…/*文字*/colorfontcontent/*边框背景 为什么要把 boder和background放在最后的原因是修改的频率会较之前的频繁&…
关于移动端rem适配
var num 1 / window.devicePixelRatio; var fontSize document.documentElement.clientWidth / 10; document.getElementsByTagName(html)[0].style.fontSize fontSize px; 适配移动端rem单位，实际使用的时候用量取到的像素值/75即为计算后的rem值，标…
JavaWeb基础—JSP
一、什么是JSP JSP 全称是 Java Server Pages，是一种开发动态web资源的技术 在原HTML上添加JAVA脚本（灵魂工程师，为页面添加灵魂），可以说 jsp html java代码 jsp标签 二、JSP的原理 JSP基本原理： JSP…
react-native 常用命令
创建项目 react-native init AwesomeProject //AwesomeProject是项目名启动 Node.js web server react-native start启动android react-native run-android启动ios react-native run-ios运行特定模拟器：react-native run-ios --simulator "iPhone 5"
使用WinPcap和libpcap类库读写pcap文件（001）开发环境配置
最近的项目要求写一个读写pcap文件的小程序，用来修改pcap中的部分信息，实现pcap的定制。 所以必须学会使用wireshark并能有利用WinPcap库和libpcap库进行开发。 虽然本文记录的都是windows下使用WinPcap进行开发，但是由于希望程序能够跨平台…
MySql忘记密码了咋办
对内 忘记密码终端修改操作： #停止mysql服务 sudo /opt/lampp/lampp stopmysql #参数启动mysqld sudo /opt/lampp/sbin/mysqld --skip-grant-tables #新建开一个终端（复制会话）进入 sudo /opt/lampp/bin/mysql -uroot #使用mysql权限&…
html资源文件记载进度条,用进度条显示文件读取进度《 HTML5：文件 API 》
在这个文档里，我添加了一个 标签 .. 上面定义了一个 ID 是 eventstatus … 我们可以把进度条放在这个容器里面 … 先找到用来显示进度条的容器 …// 找到显示事件状态的容器var eventStatus document.getElementById("eventstatus");然后再去创建进度条需…
JS中根据某个值进行大小排序
//从大到小排序 function compareBigToSmall(property){return function(a,b){var value1 a[property];var value2 b[property];return value2 - value1;} }; //从小到大排序 function compareSmallToBig(property){return function(a,b){var value1 a[property];var value…
react native 常用学习或查资料网址
react-native facebook官网：http://facebook.github.io/react-native/ 中文网：http://reactnative.cn/ react 官网地址：http://facebook.github.io/react/ Github地址：https://github.com/facebook/react 阮一峰教程：…
使用WinPcap和libpcap类库读写pcap文件（002）PCAP文件格式
本文基本翻译自https://wiki.wireshark.org/Development/LibpcapFileFormat，主要分析pcap文件的格式。 其中一些字段可能和现在的WinPcap类库里的字段不同，请结合当前WinPcap库分析。 libpcap文件格式 libpcap文件格式是TcpDump/WinDump，Wir…
图论-最短路径--3、SPFA算法O(kE)
SPFA算法O(kE) 主要思想是： 初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空时算法结束。 这个算法，简单的说就是队列优化的bellman-…
如何在HHDI中进行数据质量探查并获取数据剖析报告
通过执行多种数据剖析规则，对目标表（或一段SQL语句）进行数据质量探查，从而得到其数据质量情况。目前支持以下几种数据剖析类型，分别是：数字值分析、值匹配检查、字符值分析、日期值分析、布尔值分析、重复值…
html5网页怎么实现内容追加,纯js实现网页内容复制后自动追加自定义内容
网页操作内容复制内容后纯js实现监听自动追加自定义内容不少网站技术或者博客上有这样的处理，当我们复制代码的时候，会自动加上一段本信息版权为XXXX，这是怎么实现的呢？其实实现的方式很简单，可以在我的网站页面上绑定…
ios Standard Framework和Umbrella Framework
Standard Framework：标准库，通过引用对应的header文件而不是引用master header 文件来引用类(也可以通过引用Master Header file来引用需要使用的类)，只需要暴露对应的header文件到Header文件夹下即可，不强制引用master header文件…
Win7使用Visual Studio 2010编译用于Qt4.8.6的MySQL驱动
其实编译过程在Qt Creator 的帮助文档里有，我就是照着做的，但是没成功，因为不能照搬照抄！ 1.确保path环境变量里有QTDIR，这个就不细说了。 2.打开"开始"->"Microsoft Visual Studio 2010"->…
ios 常见性能优化
1. 用ARC管理内存 2. 在正确的地方使用reuseIdentifier 3. 尽可能使Views透明 4. 避免庞大的XIB 5. 不要block主线程 6. 在Image Views中调整图片大小 7. 选择正确的Collection 8. 打开gzip压缩 9. 重用和延迟加载Views 10. Cache, Cache, 还是Cache！ 11. 权衡渲染方…
强化学习（七）时序差分离线控制算法Q-Learning
在强化学习（六）时序差分在线控制算法SARSA中我们讨论了时序差分的在线控制算法SARSA，而另一类时序差分的离线控制算法还没有讨论，因此本文我们关注于时序差分离线控制算法，主要是经典的Q-Learning算法。 Q-Learning这一…
react遇到的各种坑
标签里用到<label for>的，for 要写成htmlFor标签里的class要写成className组件首字母一定要大写单标签最后一定要闭合如果html里要空格转义， 注意不要漏了分号;style要写成style{{clear: both,backgroundColor:red,width:200px}}组件里能用<but…
html页面视频标签,html5基础标签(html5视频标签 html5新标签用法)
点评：html5基础，包括html5视频标签和html5新标签等标签用法，大家参考使用吧1、 声明的变化2、 指定字符编码的变化，html5中建议使用utf-83、 Html5中允许没有结束符，不算错误4、 不允许写结束标记的有：…
chronyd服务
一、makestep步进时间选项 最近做RHCE的实验，nfs用krb5p实现全程加密和身份认证，需要nfs服务端、客户端的时间与KDC的时间同步，否则kerberos分发的ticket就会失效，nfs不能挂载和访问。那么就需要在nfs的服务端、客户端都配置chro…
软件测试人员必备Linux命令（初、中、高级）
有些技能可以事半功倍，有些命运掌握在我们手中。熟练的掌握和使用这些命令可以提高工作效率，并且结合这些命令对测试过程中遇到的问题进行一些初步的定位。 1 目录与文件操作 1.1 ls(初级) 使用权限：所有人 功能 : 显示指定工作目录下之内容&…