fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. mt19937_64 rd(time(0));
  5. int rand(int L, int R){
  6.     return L + rd() % (R - L + 1);
  7. }
  8.  
  9. int n, arr[10000];
  10. bool is_prime[10000];
  11.  
  12. void eratosthenes(){
  13.     memset(is_prime, 1, sizeof is_prime);
  14.     is_prime[0] = is_prime[1] = 0;
  15.  
  16.     for(int i = 2; i*i < n; i++){
  17.         if(is_prime[i]){
  18.             for(int j = i*i; j < n; j += i) is_prime[j] = 0;
  19.         }
  20.     }
  21. }
  22.  
  23. void prime_sort(){
  24.     for(int i = 0; i < n; i++){
  25.         if(is_prime[i]){
  26.             int times = i;
  27.  
  28.             while(times > 0){
  29.                 int j = rand(0, n - 1);
  30.                 if(arr[min(i, j)] < arr[max(i, j)]) swap(arr[min(i, j)], arr[max(i, j)]);
  31.                 times--;
  32.             }
  33.         }
  34.     }
  35. }
  36.  
  37. bool isSorted(int* arr, int length){
  38.     for(int i = 1; i < length; i++){
  39.         if(arr[i - 1] < arr[i]) return 0;
  40.     }
  41.  
  42.     return 1;
  43. }
  44.  
  45. int main(){
  46.     ios_base::sync_with_stdio(0);
  47.     cin.tie(0); cout.tie(0);
  48.  
  49.     cin >> n;
  50.     for(int i = 0; i < n; i++) cin >> arr[i];
  51.  
  52.     eratosthenes();
  53.  
  54.     while(!isSorted(arr, n)){
  55.         prime_sort();
  56.     }
  57.  
  58.     for(int i = 0; i < n; i++) cout << arr[i] << ' ';
  59.  
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/rZ7yRx
language:
C++14 (gcc 8.3)
created:
189 days ago
visibility:
secret

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!