例如:
#include <stdio.h>
int IsPrime(int n)
{
if (n <= 1) return 0;
if (n % 2 == 0) return n == 2;
for (int i = 3; ; i += 2)
{
if (i > n/i) break; // 等价于 i*i > n, 不用开方
if (n % i == 0) return 0;
}
return 1;
}
int main()
{
for (int n = 100; n <= 300; n++)
if (IsPrime(n))
printf("%4d", n);
return 0;
}
prime算法
prime是以点为基础出发进行检索最小生成树的一种贪心算法。
思想:
将所有的点分成两类,一类是已经放到碗里的,另一类是还没有有放到碗里的,可以通过一个数组bool visit[]来记录这个点到底是属于第一类还是属于第二类之后每一个周期索要进行的操作,找出一一定范围内路径的的范围的最小值。
所有的从第一类点直接连接到第二类点的边将最小的边记录下来(这个也就是生成树中的一条边)将这个新边(这个一个连接第一类点和第二类点的边)连到的那个第二类点归类到第一类点中,之后重复这个操作,最终消灭所有的第二类点。
假设有n个节点,我最初给出一个点,以这个点开始进行搜索,这个时候该点为第一类点,其余n-1个点为第二类点。之后进行n-1次操作,一共选出了n-1个边(符合树的性质),构成了最小生成树。
1、一般而言,prime的作用就是判断一个数是否为素数(也称“质数”)。各种函数是指自己定义的函数还是库函数?若是库函数,这就需要自己去看相关资料掌握。若是自己定义的函数,那作用自己应该清楚不过了。
2、例如:
#include <stdio.h>