Problem Solving using C++

Algorithm Study using C++

求素数的方法

过去一直用的求素数的方法为:
bool isPrime(const int n)
{
     
for(int i=2;i<=sqrt(n);i++)
       
if((n%i)==0)
          
return false;
 
          
return true;
}
但是用这种方法求从2-->n的素数的话,时间复杂度高。
今天发现一种新的方法,效率提高了很多,其核心思想如下:
bool* prime = new bool[n];

for(int i=0;i<n;i++)
prime[i]
=true;

for(int i=2;i<=sqrt(n);i++)
{
      
if(prime[i])
       {
          
for(int j=i*i;j<=n;j++)
               prime[j]
=false;
        }
}
整个测试代码如下:
#include <iostream>
#include 
<string>
#include 
<cmath>
#include 
<ctime>
#include 
<windows.h>

using namespace std;

bool
* sieve(int n)
{
    bool
* prime = new bool[n];
    
    
for(int i=0;i<n;i++)
        prime[i]
=true;
    
    prime[
0]=false;
    prime[
1]=false;
    
    
double maxsqrt=sqrt((double)n);
    
    
for(int i=2;i<=maxsqrt;i++)
    {
        
if(prime[i])
        {
            
for(int j=i*i;j<=n;j+=i)
                prime[j]
=false;
        }
    }
    
    
return prime;
}

int main(int argc,char* argv[])
{
    
int n;
    
while(1)
    {
        cin
>>n;
        
if(n==0)
            
break;
    
        DWORD start 
= timeGetTime();
        
        
        
for(int i=3;i<=n;i++)
        {
            bool flag 
= true;
            
for(int j=2;j<=sqrt(i);j++)
            {
                
if(!(i%j))
                    {
                        flag 
= false;
                        
break;
                    }
            }
            
/*
            if(flag)
                cout<<i<<" ";
                
*/
        }
        
        DWORD median 
= timeGetTime();
        
        bool
* prime = sieve(n);
        
/*
        for(int i=0;i<n;i++)
            if(prime[i])
                cout<<i<<" ";
                
*/
                
        DWORD end 
= timeGetTime();
        
        cout
<<endl;
        cout
<<(median-start)<<" ms "<<(end-median)<<" ms"<<endl;
        
        delete prime;
    }
    
    system(
"pause");
    
return 0;
}



posted on 2007-08-21 19:10 Kingoal Lee's Alogrithm Study using cplusplus 阅读(787) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜