问题 B: Prime 时间限制: 1 Sec 内存限制: 128 MB 提交: 166 解决: 78 [提交][状态][讨论版] 题目描述 Lucy give you a number n. You should tell her the maximum prime no more than n. 输入 The first line of the input gives the number of test cases, T(1
#include <stdio.h> #include <stdlib.h> #include<map> #define N 10000000 #define Max 788066 using namespace std; int prime[Max]={0}; int num_prime = 0; bool *isNotPrime; void makePrime() { for(int i = 2;i<N;i++) { if(!isNotPrime[i]) prime[num_prime++] = i; for(int j = 0;j<num_prime && i*prime[j]<N;j++) { isNotPrime[i*prime[j]] = 1; if(!(i%prime[j])) break; } } prime[num_prime++] = 10000019; } int find(int begin,int end,int temp) { // printf("%d %d %d\n",begin,end,temp); int mid = begin+end; mid/=2; if(mid==0) return 0; if(prime[mid+1]>temp && prime[mid]<=temp) return mid; else if(prime[mid]<temp) return find(mid+1,end,temp); else return find(begin,mid-1,temp); } int main() { isNotPrime = (bool*)malloc(sizeof(bool)*N); isNotPrime[0] = isNotPrime[1] = 1; makePrime(); int n; while(~scanf("%d",&n)) { for(int k = 1;k<= n;k++) { int temp; scanf("%d",&temp); int index = find(0,num_prime,temp); // printf("%d\n",index); printf("Case #%d: %d\n",k,prime[index]); } } return 0; } /************************************************************** Problem: 1012 User: T032 Language: C++ Result: 正确 Time:424 ms Memory:13800 kb ****************************************************************/