POJ 1095 Prime Cuts 素数

本文主要是介绍POJ 1095 Prime Cuts 素数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题解:

#include<cstdio>
#include<cstring>
using namespace std;const int MAX = 2000;
int p[MAX], a[MAX], pn;;void prime ()
{int i, j;memset(a,0,sizeof(a));p[1] = 1; pn = 1;for ( i = 2; i < MAX; i++ ){if ( ! a[i] ) p[++pn] = i;for ( j = 2; j <= pn && i*p[j] < MAX && ( p[j] <= a[i] || a[i] == 0 ); j++ )a[i*p[j]] = p[j];}
}int bfind ( int l, int r, int num )
{int left = l, right = r;while ( left < right ){int mid = ( left + right ) / 2;if ( num == p[mid] )return mid;if ( num < p[mid] )right = mid - 1;else if ( num > p[mid] ) left = mid + 1;}if ( num >= p[left] ) return left;else return left - 1;
}int main()
{prime();int n, c, l, r, m;while ( scanf("%d%d",&n,&c) != EOF ){m = bfind ( 1, pn, n );if ( m % 2 ){l = m / 2 - c + 2;r = m / 2 + c;}else{l = m / 2 - c + 1;r = m / 2 + c;}if ( l < 1 ) l = 1;if ( r > m ) r = m;printf("%d %d:",n,c);for ( int i = l; i <= r; i++ )printf(" %d",p[i]);printf("\n\n");}return 0;
}

这篇关于POJ 1095 Prime Cuts 素数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---