使用地图使用埃拉托色尼筛法进行记忆和素数生成

Question

#include<iostream> 
#include<map> 
#include<algorithm> 
#include<math.h>
using namespace std ; 
map< long long int , long long int > prim ;
map< long long int , long long int >::iterator it ;

int c, counter, check ;
long long int b ;
int prime( long long int t)
{  
    if( t==1 )
    {
        prim[1] = 1 ;
        counter = 1 ;
        it=prim.begin() ;
        //cout<< it->second  ;
        return 1 ;    
     }
     else
     {
         check = -1 ;
         long long int f ; 
         f= int(sqrt(t)) ; // could create prob
         for(  it=prim.begin()  ; it!= prim.end() || it->second <=f ;  it++)
         {  
             if( (t % (it->second))==0  &&  it->second != 1 )
             {
                 cout << "not prime " << "\n" ;
                 check = 0 ;
                 // not prime 
                 break ; 
             }        
         }

         if(check==-1)
         { 
             //  prime ;
             counter ++ ; 
             prim[counter] = t ; 
             return 1 ;
         }  

         else if(check==0)
             return 0 ;

     } 
 }  

 int main()
 {
     int check2 ;
     check2 = 1  ; // value set 1 to call it prime 

     cout<< "input no ";

     cout<<"\n";

     cin >>b ;

     for( long long  int z=1 ;z <=int(sqrt(b)); z++  )
     {
         c = prime(z) ;
         //cout<<"z is "<<z <<"\n";

         if ( c==1  && z!=1 )
         {
             if((b%z) == 0)
             {
                 //cout<< "not prime " ; 
                 check2 = 0 ;
                 break ;  
             }
         }
    }

    if(check2!=0)
    {
        cout<<"\n";
        cout<< "prime"  ;
    }
    else 
        cout<< "not prime " ;  

    for(  it=prim.begin()  ; it!= prim.end() ;  it++)
    { 
        cout<<"\n" ; 
        cout<< it->first ; 

        cout<< it->second ; 
        cout<< " \n"  ;

    }

    return 0 ;
}

好吧，我在处理 200 以上的素数时遇到了问题。程序没有正确执行给出意外的值。

如果你们能告诉我生成素数图的错误或更好的方法，请告诉我！

Answer 1

以下是一个模板，希望对您有所帮助，它需要 O(nlog(logn)) 时间和 O(n) 内存，如果你必须生成从 1 到 n

的所有素数

     void print_primes(int n)
     {
          int primes[n+1],start=2,i;

          /* Initialization , if primes[i]=1 it means
             i is prime and if 0 it means i is composite,
             initially assume all are prime */
          for(int i=1;i<=n;i++)primes[i]=1;

          /*Seives method*/
          while(start*start<=n)
          {
               for(i=start*start;i<=n;i=i+=start)
                  primes[i]=0;
               for(i=start+1;i<=n;i++)
               {
                   if(primes[i])
                      break;
               }
               start=i;
          }

          /*Just printing all primes from 1 to n
            if primes[i]=1 it means i is prime 
            and if 0 it means i is composite*/
          for(i=2;i<=n;i++)
          {
              if(primes[i])
                cout<<i<<endl;
          }
     }

正如 alain 所建议的，不需要地图，array/vector 只需要 fine.You 也可以检查从 1 到 1000000 的所有素数，这里使用上面的函数打印：http://coliru.stacked-crooked.com/a/b617a4d1f1d16ac5.

使用地图使用埃拉托色尼筛法进行记忆和素数生成

memoization and prime number generation using sieve of eratosthenes using maps

c++

primes

sieve-of-eratosthenes