浅析C语言中求解素数问题的算法

摘要：该文主要介绍了通过C这种语言来求解素数的问题，首先是列举了素数最为基本的判定算法，其次是使用随机产生数值的方法和基本循环控制方法来实现素数的求解应用，最后认为针对方法的选择需要根据现实应用来选择最优的实现方法。

关键词：C语言；素数；算法

中图分类号：G424 文献标识码：A 文章编号：1009-3044（2013）27-6135-03

C 语言是属于一种具有结构化的程序设计语言，它可以使每一个编写出的程序以多个结构来组成，常见的结构有顺序结构、选择结构以及循环结构这三种最为基本的结构形式，这可以使程序的整体结构变得十分的清晰以及易读性十分的强，同时也能够全面有效地提高程序设计重复利用性和代码的编写效率。循环结构在C语言中是一个很重要的组成部分。由于计算机运算速度相当快，重复性地工作是计算机的最大特色之一。程序员在进行程序编写时，人们总是会想方设法地将一些十分复杂的并且不是很易理解的求解过程全面地转化为能够较好地理解的操作次数。为有这样，才能将问题的复杂性变得简单一些，全面有效地减低程序整体设计的难度，全面有效地减少程序重复编写；同时也能够充分地发挥出计算机的整体运算速度和加快执行的优势。

1 关于素数

素数，是在数论中的一个重要议题。哪么什么是素数呢？意思是指在一个大于1的自然数中，除了l以及其本身之外，无法被其他一些自然数整除的这样数。而比1大时但是又不是素数的数可以称之为合数。1与0之间既不是素数也不是合数。素数与合数之间是属于对立的两个不同概念，这两者之间形成了数论当中最为基础的定义之一。而素数的算法也在信息学以及程序设计中得到了较为广泛的实际应用。

2 基本的素数判定算法

也就是说通常的一种求解是通过Q以内素数的一种算法。程序整体时间复杂度是O（Q*sqrt（Q）），假如Q的值比较小时，上面算法可以很容易得出结果，时间复杂度几乎可以忽略。但是从某种意义上来说，上面的算法是属于一执行效率相当低的算法，假若Q存在有大小较为接近的素因子，那么上面的算法是无法实现的。但是，当Q存在一个较小的因子时。这样的一种算法能够较快地找到这个很小的因子。值我们注意的是，对于这样的随机Q，2是属于这个因子的概率有50%以上，3作为这个因子的有33%，等等，并且88%的正整数会小于100的因子，91%的有小于1000。但是如果当Q的值很大的时候，例如Q=10000000时，那么Q*sqrt（Q）>30000000000，其数量级就会变得十分大。程序的整体效率就会变得很低，从而使人们无法忍受。所以我们应用C语言来完善素数的基本算法。

3 素数问题的应用

3.1随机数中素数算法的应用

学习程序假设只局限在素数相关定义方面就没有实际的意义了，有时候可能关系到一些深度方面的问题。下面将通过一组随机数来进一步对素数的认识（它们的取值范围是从负300～正300）。

通过上面这样的三种循环语句可以求解出素数的基本算法，同时我们也可以发现出for语句对于循环的次数以及循环增量来确定哪种循环更具优势。从理论上来讲，全部循环语句都是可以通过上述任何一个循环来实现，但是各自的优势是不一样的，所以，我们需要在现实中通过具体问题来进行具体的分析，选择适合该问题的最优实现方法。

4 结束语

综上所述，笔者通过使用随机法以及不同的循环结构解决同一问题的对比引入主题，求解素数的算法是作为求解数学问题中是最为经典的问题，可以使用在许多计算机语言中，关于算法的具体实现也是属于无止境的，需要我们大家一起共同研究。

参考文献：

[1] 周燕.用循环结构for语句解决数列前项和问题[J].信息技术教育，2004（8）.

[2] 吕凤翥.C++语言基础教程[M].北京： 清华大学出版社，2004：77-85.

[3] 高晓巍，郑大钊.查找素数的有效方法及在计算机上的实现[J].高师理科学刊，2005（8）：9.