# 【日常小测】素数

1k以内右168个素数，但第12个素数就大于33了

#include<bits/stdc++.h>
#define LL long long
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;

const int N = 1001;
const int M = 200;
const int MX = 2100;

bitset<N> vec[M],vis,ans;
int n,m,BAS[N],vout,sign,f[2][MX],w,p;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void DFS(int t) {
if (!sign && t == m+1) {
vout = max(vout, (int)vis.count());
} else if (sign && t == 12) {
int ret = 0;
for (int i=1;i<=11;i++) {
if (ans[i]) {
ret += (1<<(i-1));
}
}
f[p][ret] = max(f[p][ret],(int)vis.count());
} else {
DFS(t + 1);
for (int i=1;i*BAS[t]<=n;i++)
vis[i*BAS[t]] = vis[i*BAS[t]] ^ 1;
ans[t] = 1;
DFS(t + 1);
for (int i=1;i*BAS[t]<=n;i++)
vis[i*BAS[t]] = vis[i*BAS[t]] ^ 1;
ans[t] = 0;
}
}

int main() {
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
if (m > 12) {
w = 1; p = 0;
memset(f,0,sizeof(f));
vis.reset(); ans.reset();

for (int i=1;i<=m;i++)
sort(BAS+1,BAS+1+m);
sign = 1; DFS(1);

for (int i=12;i<=m;i++,w^=1,p^=1) {
memset(f[w],0,sizeof(f[w]));
for (int j=0,sta,tmp;j<=2047;j++) {
tmp = 0;
for (int k=1,lim=n/BAS[i];k<=lim;k++) {
sta = 0;
for (int x=1,cur=1;x<=11;x++,cur<<=1) {
if ((j&cur) && k % BAS[x] == 0)
sta ^= 1;
}
if (sta) tmp--;
else tmp++;
}
f[w][j] = f[p][j] + max(0, tmp);
}
}
for (int i=0;i<=2047;i++)
vout = max(f[p][i], vout);
printf("%d\n",vout);
} else {
vis.reset();
for (int i=1;i<=m;i++)
sign = 0; DFS(1);
printf("%d\n",vout);
}
}
return 0;
}


## 22 thoughts to “【日常小测】素数”

1. For newest information you have to pay a quick visit the
web and on web I found this site as a best site for latest updates.

2. Thanks for sharing such a nice opinion, article is pleasant,
thats why i have read it fully

3. Hello! I know this is somewhat off topic but I was
wondering which blog platform are you using for this website?
I’m getting tired of WordPress because I’ve had issues
with hackers and I’m looking at options for another platform.
I would be awesome if you could point me in the direction of a good platform.

4. I loved as much as you will receive carried out right here.
The sketch is attractive, your authored material stylish.
nonetheless, you command get bought an nervousness over that you wish be delivering the following.
unwell unquestionably come further formerly again since
exactly the same nearly a lot often inside case you shield this increase.

5. I am not sure where you are getting your information, but great topic.
I needs to spend some time learning much more or understanding more.
Thanks for great information I was looking for this information for my mission.

6. Hey there! I just wanted to ask if you ever have any issues
with hackers? My last blog (wordpress) was hacked and I ended up losing many months of hard work due
to no data backup. Do you have any solutions to prevent hackers?

7. Nice answers in return of this question with solid arguments and telling the whole thing about that.

8. Simply want to say your article is as astonishing.
The clearness for your post is just great and that i could suppose you are
an expert on this subject. Well with your permission let me to take hold of your feed

9. Woah! I’m really enjoying the template/theme of this website.
It’s simple, yet effective. A lot of times it’s difficult to get that “perfect balance” between usability and visual appeal.
I must say you’ve done a great job with this.
In addition, the blog loads very quick for me on Internet explorer.
Exceptional Blog!

10. Have you ever thought about including a little bit more
than just your articles? I mean, what you say is important and everything.
to give your posts more, “pop”! Your content is excellent but with images and clips, this site could certainly be one of the best in its
niche. Wonderful blog!

11. Hmm is anyone else experiencing problems with
the images on this blog loading? I’m trying to find out if its a problem on my end or if it’s
the blog. Any feedback would be greatly appreciated.

12. Nice weblog right here! Additionally your website so much up very fast!
What web host are you the use of? Can I am getting your

13. Hey there I am so delighted I found your blog page, I really found you by accident, while I was looking
on Digg for something else, Anyways I am here now and would just
like to say many thanks for a tremendous post and a
all round entertaining blog (I also love the theme/design), I don’t have time to read
it all at the minute but I have book-marked it and also added in your RSS feeds,
so when I have time I will be back to read more, Please
do keep up the fantastic job.

14. Hi! Someone in my Facebook group shared this website with us so I came to take
a look. I’m definitely loving the information. I’m
book-marking and will be tweeting this to my followers!
Exceptional blog and amazing style and design.

15. hey there and thank you for your information – I have certainly picked up anything new
from right here. I did however expertise several technical
points using this web site, as I experienced to reload the site a lot of times previous to
I could get it to load correctly. I had been wondering if your
web hosting is OK? Not that I’m complaining, but sluggish loading instances times will often affect
Anyway I am adding this RSS to my e-mail and can look out for much more
of your respective interesting content. Make sure you update this again soon.

16. I’m really enjoying the design and layout of your site. It’s a
very easy on the eyes which makes it much more enjoyable for me
to come here and visit more often. Did you hire out
a developer to create your theme? Superb work!

17. Hey there, I think your website might be having browser compatibility issues.

When I look at your blog site in Firefox, it looks fine
but when opening in Internet Explorer, it has some overlapping.

I just wanted to give you a quick heads up! Other then that,
very good blog!

18. Whats up very cool website!! Guy .. Beautiful .. Wonderful ..