打印质数的算法应该是学习计算机编程的一个经典的问题,在这里想给大家展示一些方法,相信这些方法会对你的编程有一定的启发作用。请你注意几点,
- 实际应用和教学应用有很大的差别。
- 最后的那个使用编译时而不是运行时的方法大家可以重点看看。
教科书的示例
首先,先给一个教科书的示例。下面这个示例应该是教科书(至少是我上大学时的教科学)中算法复杂度最好的例子了。其想法很简单,先写一个判断是否是
质数的函数isPrime(),然后从1到n分别调用isPrime()函数来检查。检查是否是质数的算法是核心,其简单的使用从2到n的开根的数作为除
数。这样的算法复杂度几乎是O(n*log(n)),看上去不错,但其实很不经济。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>
using
namespace
std;
bool
isPrime(
int
nr)
{
for
(
int
d = 2; (d * d) < (nr + 1); ++d){
if
(!(nr % d)){
return
false
;
}
}
return
true
;
}
int
main (
int
argc,
char
*
const
argv[])
{
for
(
int
i = 0; i < 50; ++i){
if
(isPrime(i)){
cout << i << endl;
}
}
}
|
较好的算法
我们知道,我们的算法如果写成线性算法,也就是O(n),已经算是不错了,但是最好的是O(Log(n))的算法,这是一个级数级的算法,著名的二分取中(Binary Search)正是O(Log(n))的算法。通常来说,O(Log(n))的算法都是以排除法做为手段的
。所以,找质数的算法完全可以采用排除法的方式。如下所示,这种算法的复杂度是O
(n(log(logn)))。
示例:打印30以内的质数
一、初始化如下列表。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
二、把第一个数(2)取出来,去掉所有可以被2整除的数。
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
三、取第二个数(3),去掉所有可以被 3整除的数。
2 3 5 7 11 13 17 19 23 25 29
四、取第三个数(5),因为4已经被去除了,再去掉所有可以被5整除的数。
2 3 5 7 11 13 17 19 23 29
接下来的数是7,但是7的平方是49,其大于了30,所以我们可以停止计算了。剩下的数就是所有的质数了。
实际应用的算法
实际应用中,我们通常不会使用上述的两种算法,因为那是理论学院派的算法。实际中的算法是,我把质数事先就计算好,放在一个文件中,然后在程序启动
时(注意是在启动时读这个文件,而不是运行时每调用一次就读一次文件),读取这个文件,然后打印出来就可以了。如果需要查找的化,二分查找或是hash表
查找将会获得巨大的性能提升。当然,这样的方法对于空间来说比前面两个都要消耗得大,但是你可以有O(log(n))或是O(1)的时间复杂度。
所以,我想在这里提醒大家——实际和理论的的方法很不一样的
,千万不要读书读成书呆子。在游戏编程的世界里,大量的数据都不是运行计算的,而都是写在文件中的。比如,一个火焰效果,一个人物跑动的动作,都是事先写在文件中的。
使用编译时而不是运行时
下面这个例子(本例参考于这里
)你需要注意了,这是一个高级用法,使用模式来在编译时计算质数,而不是运行时。这种技术使用了C++编译器对模板的特化时的处理来生成自己相要的结果。这种方法在技术上是相当Cool的,但并不一定实用,这里只是想像大家展示这种用法。这是C++的最骨灰级的用法了。
请看下面的两个模板类,第一个模板以递归的方式检查是否是质数,第二个方法是递归的退出条件(当N=1时),对于模板的重载,请参看相关的C++书籍。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
template
<
int
N,
int
D = N - 1>
struct
isPrime {
enum
{
result = (N % D) && isPrime<N, D-1>::result
};
};
template
<
int
N>
struct
isPrime<N, 1> {
enum
{
result =
true
};
};
|
于是,通过这个模板,我们可以使用下面的代码来检查是否是质数:
1
2
|
if
(isPrime<3>::result)
cout <<
"Guess what: 3 is a prime!"
;
|
下一步,我们需要打出一个区间内的质数,所以,我们需要继续设计我们的print模板。
1
2
3
4
5
6
7
8
9
10
11
|
template
<
int
N,
bool
ISPRIME>
struct
printIfPrime {
static
inline
void
print() {}
};
template
<
int
N>
struct
printIfPrime<N,
true
> {
static
inline
void
print() {
std::cout << N << endl;
}
};
|
从上面的代码中,我们可以看到,我们的第一个实际是什么也没做,而第二个有输出,注意第二个的模板参数中有一个true,其意味着那个质数的判断。于是我们就可以给出下面的代码来尝试着打印出一段区间内的质数:(请不要编译!!
因为那会让编译器进入无限循环中,原因是printPrimes会不停地调用自己永不停止)
1
2
3
4
5
6
7
8
|
template
<
int
N,
int
MAX>
struct
printPrimes {
static
inline
void
print()
{
printIfPrime<N, isPrime<N>::result>::print();
printPrimes<N + 1, MAX>::print();
}
};
|
为了避免这个问题,你需要再加一个模板类,如下所示。这样当N变成MAX的时候,递归就结束了。
1
2
3
4
5
6
|
template
<
int
N>
struct
printPrimes<N, N> {
static
inline
void
print() {
printIfPrime<N, isPrime<N>::result>::print();
}
};
|
最后,让我们来看看最终的调用:
1
2
3
4
5
|
int
main (
int
argc,
char
*
const
argv[])
{
printPrimes<2, 40>::print();
return
0;
}
|
这个方法很NB,但是有两个问题:
不过,相信这种玩法会启动你很多的编程思路。
当然,还有以前说过的那个——《检查素数的正则表达式
》
原文地址:http://coolshell.cn/articles/3738.html
分享到:
相关推荐
概率算法求素数(c语言)
单片机C语言常用算法是指在单片机系统中使用C语言实现的算法,包括计数、求和、求阶乘、求最大公约数、最小公倍数、判断素数、验证哥德巴赫猜想等。这些算法都是解决实际问题的基本思想方法和步骤。 一、计数、求和...
全排序、二分查找、冒泡排序、阶乘、最大公约数、最小公倍数、打印九九乘法表、判断素数、快速排序的递归实现和非递归实现、随机数、字符串操作、50人围成一圈,数到3和3的倍数的人出局,最后剩下的人是谁。...
设计程序求任意给定范围之间的素数 int main(int argc, char* argv[]) { int min_size,max_size;... //打印计算出的素数 print_prime( data, max_size,min_size); system("pause"); return 0; }
1. 1 - 100, 找出质数 2. 冒泡排序 3. 1~100共一百个自然数,放入一个只有99个元素的数组中,找出没有被放入数组的这个数; 4. 字符串的反转输出 5. 截取字符串, 如果该字符串是“abc我的”,当截取的字节数是3时候...
C#取1000以内质数并按三角形输出 //2 //3 5 7 //11 13 17 19 23 //29 31 37 41 43 47 53 //59 61 67 71 73 79 83 89 97 //.................................................
打印所有素数直到给定 n。 定理:假设所有数字都是素数,直到被证明为假。 单链表 标准单向链表:push/pop front、insert(i)、remove(i)、reverse、removeValue 使用带有尾指针的单向链表的队列实现。 二分搜索...
(1)如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可。 (2)如果n <> k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你,重复执行第一步。 (3)如果n不能被k整除,则用k 1...
4.求100-200之间的素数(只能被1和自身整除),并输出。5.非波拉契数列问题。6.sum=a+aa+aaa+aaaa+...7.给一个不多于5位的正整数,求是几位数,并逆序打印各个数字8.排序9.杨辉三角10.n个人围成圈,顺序排号,从第一...
然后在 main 函数中,通过一个循环来检查从2到999(这里假设我们只需要检查小于1000的数)的所有数,如果一个数既是素数又是回文数,就将其打印出来。 请注意,这个程序只检查了小于1000的数。如果需要检查更大的...
101-200素数、阿拉伯数字转化为罗马数字、打印金字塔、二分查找、回文数、矩阵转置、冒泡排序、判断闰年、最大公约数......
在实际应用中,我们可以使用搜索与回溯算法来解决各种问题,例如素数环问题。在这个问题中,我们需要从 1 到 20 这 20 个数摆成一个环,要求相邻的两个数的和是一个素数。我们可以使用搜索与回溯算法来解决这个问题...
搜索与回溯算法 搜索与回溯算法是一种常用的算法,在计算机科学中具有重要的地位。回溯是搜索算法中的一种控制策略,通过不断地搜索和回溯,来求解问题。基本思想是:为了求得问题的解,先选择某一种可能情况向前...
然后在 main 函数中,通过一个循环来检查从2到999(这里假设我们只需要检查小于1000的数)的所有数,如果一个数既是素数又是回文数,就将其打印出来。 请注意,这个程序只检查了小于1000的数。如果需要检查更大的...
质数(素数)在公钥加密算法(如RSA)中有重要的应用。 3 如何判断一个数是否为质数(素数) 判断一个数是质数(素数),还是合数,可以根据它的约数的个数来确定:只有两个 约数的数,是质数;有三个或三个以上的...
《妙趣横生的算法(C语言实现)》可作为算法入门人员的教程,也可以作为学习过C语言程序设计的人士继续深造的理想读物,也可作为具有一定经验的程序设计人员巩固和提高编程水平,查阅相关算法实现和数据结构知识的参考...
本文实例讲述了Python实现输出某区间范围内全部素数的方法。分享给大家供大家参考,具体如下: # -*- coding: utf-8 -*- # 简述:区间范围101-200 # 要求:判断这个区间内有多少个素数,并逐一输出。 def prime(m,n...
试求出所有满足这个要求的各种数字填法。 //我们可以通过改变N的值来求不同数字范围的质数数组,如果超出整型的范围,还需要改变数据类型。 //f[i]来记录数字i是否使用过, //T[i]用来记录下一个可以插在数字i后面...
【程序1】 题目:判断101-200之间有多少个素数,并输出所有素数。 1.程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 public class exp2{ public...