запоминание и генерация простых чисел с помощью решета эратосфена с использованием карт

#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, и они являются простыми. программа не выполняется должным образом, выдавая непредвиденные значения.

если вы, ребята, могли бы рассказать мне об ошибках или лучших способах создания карты простых чисел, пожалуйста!


person v_g    schedule 10.02.2015    source источник
comment
Начнем с того, что a, c,d , h , i ,j , k , l, b не являются хорошими именами для переменных; на чтение и понимание программы с такими именами уходит гораздо больше времени; и труднее самому найти проблемы...   -  person Alex Shesterov    schedule 10.02.2015
comment
Кроме того, C++ позволяет вам объявлять переменные в тот момент, когда они вам впервые понадобятся; нет необходимости объявлять все глобально.   -  person Alex Shesterov    schedule 10.02.2015
comment
Пожалуйста, исправьте форматирование.   -  person genisage    schedule 10.02.2015
comment
Почему map? Для этого лучше подойдет простой vector.   -  person alain    schedule 10.02.2015
comment
@alain Мне еще не приходилось сталкиваться с векторами, я читал о картах и, следовательно, пытался их реализовать. я поищу это. Благодарю .   -  person v_g    schedule 10.02.2015
comment
@AlexShesterov, ммм, извини. не повторится.   -  person v_g    schedule 10.02.2015


Ответы (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, нет необходимости в карте, массив/вектор подойдет. Вы также можете проверить все простые числа от 1 до 1000000, напечатанные с помощью вышеуказанной функции здесь: http://coliru.stacked-crooked.com/a/b617a4d1f1d16ac5.

person sashas    schedule 10.02.2015
comment
while(start<=sqrt(n)) можно изменить на while(start*start<=n), таким образом обойдя дорогостоящую функцию sqrt. Тоже i=i+=start что? - person P i; 11.02.2015
comment
если вы хотите придать ему дополнительный вид, вы можете дать ссылку на работающий coliru.stacked-crooked.com код. - person P i; 11.02.2015
comment
@Pi спасибо не знал об этом онлайн редакторе , добавил ссылку - person sashas; 11.02.2015
comment
Спасибо @sasha, но если вы найдете ошибку в моем коде, пожалуйста, дайте мне знать. Хотя у тебя исполнение лучше. - person v_g; 11.02.2015