fork download
copy 
  1. // Long Challenge
  2.  
  3. #pragma Gpref optimize("O3")
  4. //#pragma Gpref optimize("Ofast")
  5. //#pragma Gpref target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6. //#pragma Gpref optimize("unroll-loops")
  7. #include <bits/stdc++.h>
  8. #define int long long
  9. #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  10. #define FR(i,j,k) for(int i=j; i<k; i++)
  11. #define TC int T; cin >> T; FR(t,0,T)
  12. #define BFR(i,j,k) for(int i=j; i>=k; --i)
  13. #define pb push_back
  14. #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  15. #define go continue
  16. #define F first
  17. #define S second
  18. using namespace std;
  19.  
  20. const int MOD = (int)1e9+7;
  21. const int N = 1e4+4;
  22.  
  23.  
  24. int32_t main(){
  25. IOS;
  26.  
  27. //TC{
  28. 	int n,c=0,x;
  29. 	cin >> n;
  30. 	vector<int> v(n);
  31. 	bool spf[N+1];
  32. 	memset(spf,true,N+1);
  33. 	map<int,int> parent;
  34. 	for(int i=2; i<=N; ++i){
  35. 		if(spf[i]){
  36. 			parent[i] = i;
  37. 			for(int j=i*i; j<=N; j+=i){
  38. 				parent[j] = i;
  39. 				spf[j] = false;
  40. 			}
  41. 		}
  42. 	}
  43. 	set<int> colors;
  44. 	FR(i,0,n){
  45. 		cin >> x;
  46. 		colors.insert(parent[x]);
  47. 	}
  48.  
  49. 	cout << colors.size() << '\n';
  50. //}
  51. 	return 0;
  52. }
  53.  
  54.  
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
3
10 7 15
stdout
copy 
3
https://ideone.com/6oweVp
language:
C++14 (gcc 8.3)
created:
4 years 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!