題意: 給一個區間 [ L, U ] ( 1 <= L,U <= 2147483647 & (U-L) <= 1000000 )，求此區間內，距離最近、最遠的兩相鄰質數。
解法: 質數篩選，由於區間大小最大不超過 10^6 ，所以可以像埃拉托斯特尼篩法來篩掉這個區間內的質數，再找答案即可。
TAG: Prime
注意:
程式碼:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Tittle: 10140 - Prime Distance | |
| * Author: Cheng-Shih, Wong | |
| * Date: 2015/04/09 | |
| */ | |
| // include files | |
| #include <iostream> | |
| #include <cstdio> | |
| #include <cstring> | |
| using namespace std; | |
| // definitions | |
| #define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i ) | |
| #define clr(x,v) memset( x, v, sizeof(x) ) | |
| #define N 1000005 | |
| typedef long long ll; | |
| // declarations | |
| ll l , u; | |
| bool isprime[50005]; | |
| ll prime[25000]; | |
| int pcnt; | |
| ll last; | |
| ll minl, minu, maxl, maxu, mind, maxd; | |
| int cnt; | |
| // functions | |
| ll find( ll start, ll div ) | |
| { | |
| ll k = start/div; | |
| if( start%div ) ++k; | |
| if( k==1LL ) ++k; | |
| return k*div; | |
| } | |
| void solve( void ) | |
| { | |
| static bool enable[N]; | |
| static ll delta; | |
| clr( enable, true ); | |
| for( int i=1; i<=pcnt && prime[i]*prime[i]<=u; ++i ) { | |
| for( ll j=find(l,prime[i]); j<=u; j+=prime[i] ) | |
| enable[j-l] = false; | |
| } | |
| last = 0LL; | |
| cnt = 0; | |
| mind = u-l+1LL; | |
| maxd = 0LL; | |
| for( ll i=l; i<=u; ++i ) if( enable[i-l] ) { | |
| if( i==1LL ) continue; | |
| if( last ) { | |
| // printf( "(%lld,%lld)\n", last, i ); | |
| delta = i-last; | |
| if( delta > maxd ) { | |
| maxd = delta; | |
| maxl = last; | |
| maxu = i; | |
| } | |
| if( delta < mind ) { | |
| mind = delta; | |
| minl = last; | |
| minu = i; | |
| } | |
| } | |
| last = i; | |
| ++cnt; | |
| } | |
| } | |
| // main function | |
| int main( void ) | |
| { | |
| // init | |
| pcnt = 0; | |
| clr( isprime, true ); | |
| isprime[0] = isprime[1] = false; | |
| for( ll i=2LL; i<=50000LL; ++i ) if( isprime[i] ) { | |
| prime[++pcnt] = i; | |
| for( ll j=i*i; j<=50000; j+=i ) | |
| isprime[j] = false; | |
| } | |
| // input | |
| while( scanf( "%lld%lld", &l, &u )==2 ) { | |
| // solve | |
| solve(); | |
| // output | |
| if( cnt > 1 ) | |
| printf( "%lld,%lld are closest, %lld,%lld are most distant.\n", minl, minu, maxl, maxu ); | |
| else | |
| puts("There are no adjacent primes."); | |
| } | |
| return 0; | |
| } |
沒有留言:
張貼留言
任何意見都樂意傾聽