使用筛选法求100以内的素数
筛选法介绍
先把N个自然数按次序排列起来。 1不是质数，也不是合数，划去。 第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没
划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。
这其实是一种很粗暴的解法, 去逐个整除质数!
程序流程
* 将N个自然数写入到一个数组中, 1划掉(设置为0)
* 2后面所有能够整除2的数, 划掉(置0)
* 设2后面的第一个非0数就是第二个质数设置为N, 将N后所有能够整除N的数, 划掉
* 以此类推
实际代码
#include<stdio.h>
#include<math.h>
#include <vector>
static void prime_number(int num)
{
std::vector<int> pm(num);
for(int i = 0; i < num; i++)
{
pm[i] = i + 1;
}
pm[0] = 0; //1不是素数
for(int i = 1; i < num - 1; i++)
{
for(int j = i + 1; j < num; j++)
{
if(pm[i] && pm[j] && 0 == pm[j] % pm[i])
{
pm[j] = 0;
}
}
}
int k = 1;
for(auto c : pm)
{
if(c)
{
printf("%d\t", c);
k++;
}
if(k % 10 == 0)
{
printf("\n");
k++;
}
}
printf("\n");
}
int main()
{
prime_number(128);
system("pause");
return 0;
}
上一次写字符串RK算法时, 计算
hash可以以每一个字符指代要给素数更好, 当时查了一下素数的求解方式
不过感觉实际没有必要去求一定数量的素数, 因为如果少量的话直接求出来放在数组里面就可以了, 非常多的话那么算法也绝不是这么简单!
