2013年10月13日 星期日

STEP5 0005 Ch1-2.梗賤橋

[質數篩子]
只要用質數的篩子觀念處理即可。
複雜度是 nlg(lgn)
重點在於欲處理後的判斷"至否為質數"的三個條件





 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<vector>
#define N 1000000
bool seive[N+1];
int nptr[N+1];
int RES[N+1];
std::vector<int>prime;
int main()
{
 memset(seive,true,sizeof(seive));
 seive[1]=false;
 for(int lx=2;lx<=N;lx++)
 {
  if(seive[lx])
  {
   prime.push_back(lx);
   for(int ly=2;ly*lx<=N;ly++)
    seive[lx*ly]=false;
  }
 }
 for(int ly=1;ly<=N;ly++)
  nptr[ly]=ly;
 for(int lx=0;lx<prime.size();lx++)
 {
  int tmp;
  if((N/prime[lx])<=1)
   break;
  for(int ly=(N/prime[lx]);ly>=2;ly--)
  {
   tmp=nptr[prime[lx]*ly];
   nptr[prime[lx]*ly]=nptr[prime[lx]*(ly-1)];
   nptr[prime[lx]*(ly-1)]=tmp;
  }
 }
 for(int lx=1;lx<=N;lx++)
  RES[nptr[lx]]=lx;
 free(nptr);
 //for(int lx=1;lx<=N;lx++)
 // assert((RES[lx]>0)&&((RES[lx]>=lx)||seive[RES[lx]]));
 int nn,M;
 int T,lT;scanf("%d",&T);
 for(lT=1;lT<=T;lT++)
 {
  scanf("%d %d",&nn,&M);
  if((RES[M]>nn)||seive[RES[M]]||(RES[M]<M))
   printf("Geng Jian malheureux roi mauvaise!!\n");
  else
   printf("%d\n",RES[M]);
 }
 return 0;
}

沒有留言:

張貼留言