首页 > 代码库 > hdu--5108--数论

hdu--5108--数论

2024-08-03 20:12:55   212人阅读

数据因为很大 达到 max=1e9

首先 素数筛选出 sqrt(max)的范围内有多少素数

然后 对于每个n  求出它的所有因子 sort一遍后 从小到大开始遍历过去

特判下 对于n大于 sqrt(max)的情况下 是否为素数的情况 因为N>1e6的情况不超过100组 所以不会特判很多次的

 

 1 #include <iostream> 2 #include <vector> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6  7 const int size = 100000; 8 bool vis[size+10]; 9 vector<int>ve;10 11 void init( )12 {13     memset( vis , true , sizeof(vis) );14     vis[0] = vis[1] = false;15     for( int i = 2 ; i<=size ; i++ )16     {17         if( vis[i] )18         {19             int j = i * 2;20             while( j<=size )21             {22                 vis[j] = false;23                 j += i;24             }25         }26     }27 }28 29 void solve( int n )30 {31     ve.clear();32     for( int i = 1 ; i*i<=n ; i++ )33     {34         if( n%i==0 )35         {36             ve.push_back( i );37             if( i*i!=n )38                 ve.push_back( n/i );39         }40     }41     sort( ve.begin() , ve.end() );42 }43 44 bool judge( int x )45 {46     if( x%2==0 )47         return false;48     for( int i = 3 ; i*i<=x ; i+=2 )49     {50         if( x%i==0 )51             return false;52     }53     return true;54 }55 56 int main()57 {58     int n , ans , cnt;59     bool flag;60     init( );61     while( ~scanf("%d",&n) )62     {63         solve( n );64         cnt = ve.size();65         ans = 0;66         flag = false;67         for( int i = 0 ; i<cnt ; i++ )68         {69             if( n/ve[i]>size )70             {71                 flag = judge( n/ve[i] );72                 if( flag )73                 {74                     ans = ve[i];75                     break;76                 }77             }78             else if( vis[ n/ve[i] ] )79             {80                 ans = ve[i];81                 break;82             }83         }84         printf( "%d\n",ans );85     }86     return 0;87 }
View Code

 

hdu--5108--数论


联系
我们