1. #include <stdio.h>
  2.  
  3. int primechk(int num);
  4.  
  5. int get(int a, int b, int c);
  6.  
  7. int find(int arr[], int n, int target);
  8.  
  9.  
  10.  
  11. int main(){
  12.  
  13.  
  14.  
  15.  
  16.     int i,j,k,tmp,tmp2,tests;
  17.  
  18.     scanf("%d", &tests);
  19.  
  20.  
  21.  
  22.  
  23.     int* arr = (int*)malloc(tests*sizeof(int));
  24.  
  25.     char str[100][500];
  26.  
  27.  
  28.  
  29.  
  30.     for(i=0; i<tests; i++){
  31.  
  32.         scanf("%d", &arr[i]);
  33.  
  34.         scanf("%s", &str[i][0]);
  35.  
  36.     }
  37.  
  38.  
  39.  
  40.  
  41.     int primes[12];
  42.  
  43.     j=0;
  44.  
  45.     for(i=65; i<=90; i++){
  46.  
  47.         if(primechk(i)==1){
  48.  
  49.             primes[j]=i;
  50.  
  51.             j++;
  52.  
  53.         }
  54.  
  55.     }
  56.  
  57.     for(i=97; i<=122; i++){
  58.  
  59.         if(primechk(i)==1){
  60.  
  61.             primes[j]=i;
  62.  
  63.             j++;
  64.  
  65.         }
  66.  
  67.     }
  68.  
  69.     
  70.  
  71.  
  72.  
  73.  
  74.     for(i=0; i<tests; i++){
  75.  
  76.         for(j=0; j<arr[i]; j++){
  77.  
  78.             if(str[i][j]<65 ){
  79.  
  80.                 printf("C");
  81.  
  82.                 continue;
  83.  
  84.             }
  85.  
  86.             if(str[i][j]>122){
  87.  
  88.                 printf("%c", 113);
  89.  
  90.                 continue;
  91.  
  92.             }
  93.  
  94.             if(primechk(str[i][j])==1){
  95.  
  96.                 printf("%c", str[i][j]);
  97.  
  98.                 continue;
  99.  
  100.             }
  101.  
  102.             else{
  103.  
  104.                 tmp = find(primes,12,str[i][j]);
  105.  
  106.                 printf("%c", tmp);
  107.  
  108.             }
  109.  
  110.         }
  111.  
  112.         printf("\n");
  113.  
  114.     }
  115.  
  116. }
  117.  
  118.  
  119.  
  120.  
  121. int primechk(int num){
  122.  
  123.     int i;
  124.  
  125.     for(i=2; i<=num/2; i++){
  126.  
  127.         if(num%i==0){
  128.  
  129.             return 0;
  130.  
  131.         }
  132.  
  133.     }
  134.  
  135.     return 1;
  136.  
  137. }
  138.  
  139.  
  140.  
  141.  
  142. int get(int val1, int val2, int target){
  143.  
  144. if (target-val1 > val2-target)
  145.  
  146. return val2;
  147.  
  148. else
  149.  
  150. return val1;
  151.  
  152. }
  153.  
  154.  
  155.  
  156.  
  157. int find(int arr[], int n, int target){
  158.  
  159.  
  160.  
  161. if (target <= arr[0])
  162.  
  163. return arr[0];
  164.  
  165. if (target >= arr[n - 1])
  166.  
  167. return arr[n - 1];
  168.  
  169.  
  170.  
  171. int i=0,j=n,m;
  172.  
  173. while (i < j) {
  174.  
  175.  
  176.  
  177.         m = (i+j) / 2;
  178.  
  179.  
  180.  
  181. if (arr[m] == target)
  182.  
  183. return arr[m];
  184.  
  185.  
  186.  
  187. if (target < arr[m]) {
  188.  
  189. if (m>0 && target>arr[m-1])
  190.  
  191. return get(arr[m - 1], arr[m], target);
  192.  
  193. j = m;
  194.  
  195. }
  196.  
  197. else {
  198.  
  199. if (m<n-1 && target<arr[m+1])
  200.  
  201. return get(arr[m],
  202.  
  203. arr[m+1], target);
  204.  
  205. i = m+1;
  206.  
  207. }
  208.  
  209. }
  210.  
  211. return arr[m];
  212.  
  213. }
Language: C