问题说明:
除了自身之外，无法被其它整数整除的数称之为质数，要求质数很简单，但如何快速的求出质数则一直是程式设计人员与数学家努力的课题， 在这边介绍一个着名的 Eratosthenes求质数方法。
解法:
首先知道这个问题可以使用回圈来求解，将一个指定的数除以所有小于它的数，若可以
整除就不是质数，然而如何减少回圈的检查次数？如何求出小于N的所有质数？
我们先来看一个丧心病狂的低效率的解决方式:
//检验质数
bool checkZS(int a)
{
for (int i = ;i < a;i++)
{
if ( == a%i)
{
return false;
}
}
return true;
}
首先我们写一个检验质数的函数,下面我们在主函数调用:
int n = ;
clock_t start,end;//用于计时
start = clock() ;
for(int i = ;i <= n;i++)
{
if (checkZS(i))
{
cout<<i<<" ";
}
}
end = clock();
cout<<"\n总共花费了"<<(long double)(end - start)/CLK_TCK<<"秒"<<endl;
好了,让我们看下在99999以内的质数算出来的运行结果:
时间花费了17秒,太慢了;下面我们想想怎样来改进算法!
首先知道这个问题可以使用回圈来求解，将一个指定的数除以所有小于它的数，若可以整除就不是质数，然而如何减少回圈的检查次数？如何求出小于N的所有质数？
首先假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了，道理很简单，假设A*B = N，如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到这个数可以整除N。 不过在程式中使用开根号会精确度的问题， 所以可以使用 i*i <= N进行检查， 且执行更快 。
再来假设有一个筛子存放1～N，例如：
2 3 4 5 6 7 8 9 10 11 12 ........N
先将2的倍数筛去：
2 3 5 7 9 11 13........N
再将3的倍数筛去：
2 3 5 7 11 13 17 19........N
再来将5的倍数筛去，再来将7的质数筛去，再来将11的倍数筛去........，如此进行到最后留下的数就都是质数，这就是Eratosthenes筛选方法（Eratosthenes Sieve Method）
检查的次数还可以再减少，事实上，只要检查6n+1与6n+5就可以了，也就是直接跳过2与3的倍
数，使得程式中的if的检查动作可以减少。
下面我们上代码:
/*
问题:
除了自身之外，无法被其它整数整除的数称之为质数，要求质数很简单，但如何快速的
求出质数则一直是程式设计人员与数学家努力的课题， 在这边介绍一个着名的 Eratosthenes求质
数方法。
2013/7/18
张威
*/
#include <iostream>
#include <time.h>
using namespace std; #define n 99999 int main()
{
int a[n+];//建立一个数组,使a[i] == i,这样通过筛选,将非质数所在位置置0
for (int i = ;i <= n;i++)
{
a[i] = i;
}
clock_t start,end;//用于计时
start = clock() ; //每次进行筛选的数,进行优化,实际上只要筛选到 N开放就行
for (int i = ;i*i <= n;)
{
//从i处开始筛选(比i小的肯定不能被i整除)
for (int j = i;j <= n;j++)
{
//通过while循环.跳过中间置0区域
while( == a[j] && j <= n)
{
j++;
}
//假如a[j]能被i整除而且不相等(也就是说不是本身),就把这个位置数值置为0
if ( == a[j]%i && i != a[j])
{
a[j] = ;
}
}
//i的步进值优化,即跳过2或3的倍数,每次递增数加大
if((i-)% == )
i += ;
else if((i-)% == )
{
i += ;
}
else
{
i++;
}
}
end = clock();
for(int i = ;i <= n;i++)
{
if (a[i] != )
{
cout<<a[i]<<" ";
}
}
cout<<"\n总共花费了"<<(long double)(end - start)/CLK_TCK<<"秒"<<endl;
return ;
}
Eratostheness
上面标出了在减少算法中循环次数的优化方面所进行的修改,下面是运行结果:
两者之间的差距的话.......不说了,自己写的东西和这些算法相比就是渣渣!
下面上示例上面的代码:
#include <stdio.h>
#include <stdlib.h>
#define N 1000
int main(void) {
int i, j;
int prime[N+];
for(i = ; i <= N;i++)
prime[i] = ;
for(i = ; i*i <= N;i++) { // 这边可以改进
if(prime[i] == ) {
for(j = *i; j <= N;j++) {
if(j % i == )
prime[j] = ;
}
}
}
for(i = ; i < N;i++) {
if(prime[i] == ) {
printf("%4d ", i);
if(i % == )
printf("\n");
}
}
printf("\n");
return ;
}
示例代码
可以看到其实还是上面自己写的在示例的基础上还是做了些改善的!