wenbao与反素数

 1 #include <iostream>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 #define LL long long
 6 const int N = 500010;
 7 const int M = 1024;
 8 
 9 struct node {
10     int a, b;
11     node() {}
12     node(int x, int y) : a(x), b(y) {}
13     bool operator < (const node cmp) const {
14         return b < cmp.b;
15     }
16 }f[M];
17 
18 bool vis[M];
19 int prime[M];
20 int cnt, num;
21 
22 void get_prime() {
23     int i, j;
24     memset(vis, true, sizeof(vis));
25     for(i = 2; i < M; ++i) {
26         for(j = i*i; j < M; j += i) {
27             vis[j] = false;
28         }
29     }
30     cnt = 0;
31     for(i = 2; i < M; ++i) {
32         if(vis[i])  prime[cnt++] = i;
33     }
34 }
35 
36 void solve(int pnum, int val, int pos, int lim) {
37     if(val > N) return ;
38     f[num++] = node(pnum, val);
39     LL nlim, nval, npnum;
40     nval = val; nlim = 0; npnum = 1;
41     while(nlim < lim && nval <= N) {
42         nlim++; npnum++; nval *= prime[pos];
43         if(nval <= N)   solve(npnum*pnum, nval, pos + 1, nlim);
44     }
45 }
46 void get_antiprime() {
47     get_prime();
48     num = 0;
49     solve(1, 1, 0, 32);
50     sort(f, f + num);
51     for(int i = 0; i < num; ++i){
52         printf("%d--%d\n", f[i].a, f[i].b);
53     }
54 }
55 int main(){
56     get_antiprime();
57     return 0;
58 }
59 
60 
61 const int antiprime[]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,  
62                        1260,1680,2520,5040,7560,10080,15120,20160,25200,  
63                        27720,45360,50400,55440,83160,110880,166320,221760,  
64                        277200,332640,498960,554400,665280  
65                       };  
66   
67 const int factorNum[]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,  
68                        64,72,80,84,90,96,100,108,120,128,144,160,168,180,  
69                        192,200,216,224  
70                       }; 

 1 2
 2 3
 3 4
 4 5
 5 6
 6 7
 7 8
 8 9
 9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 #include<iostream>
32 #include<cstdio>
33 #include<cstring>
34 #define inf 0x7fffffff
35 #define ll long long 
36 using namespace std;
37 int n,ans=1,num=1;
38 int p[15]={1,2,3,5,7,11,13,17,19,23,29,31};
39 void dfs(int k,ll now,int cnt,int last)
40 {
41     if(k==12)
42     {
43         if(now>ans&&cnt>num){ans=now;num=cnt;}
44         if(now<=ans&&cnt>=num){ans=now;num=cnt;}
45         return;
46     }
47     int t=1;
48     for(int i=0;i<=last;i++)
49     {
50         dfs(k+1,now*t,cnt*(i+1),i);
51         t*=p[k];
52         if(now*t>n)break;
53     }
54 }
55 int main()
56 {
57     scanf("%d",&n);
58     dfs(1,1,1,20);
59     printf("%d",ans);
60     return 0;
61 }