fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxM=1e5;
  5. vector<int> divP[maxM+1];
  6. bool tag[maxM+1]={};
  7.  
  8. int main(){
  9. 	for(int m=1; 2*m<=maxM; m++)
  10. 	 divP[2*m].push_back(2);
  11. 	 for(int m=3; m<=maxM; m+=2){
  12. 	 	if(!divP[m].empty())
  13. 	 	 continue;
  14. 	 	for(int p=1; m*p<=maxM; p++)
  15. 	 	 divP[m*p].push_back(m);
  16. 	 }
  17. 	//
  18. 	int N, M, v;
  19. 	cin>>N>>M;
  20. 	for(int i=0; i<N; i++){
  21. 		cin>>v;
  22. 		for(int prime: divP[v]){
  23. 			if(tag[prime])
  24. 			 continue;
  25. 			for(int p=1; prime*p<=M; p++)
  26. 			 tag[prime*p]=1;
  27. 		}
  28. 	}
  29. 	int ans=0;
  30. 	for(int m=1; m<=M; m++)
  31. 	 ans+=tag[m]==0;
  32. 	cout<<ans<<'\n';
  33. 	for(int m=1; m<=M; m++)
  34. 	 if(tag[m]==0)
  35. 	  cout<<m<<'\n';
  36. 	return 0;
  37. }
Success #stdin #stdout 0.02s 9016KB
comments (?)
stdin
copy 
3 12
6 1 5
stdout
copy 
3
1
7
11
https://ideone.com/oUp9DG
Coprime 2
language:
C++14 (clang 8.0)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!