fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.  static int gcd(int a, int b) {
  11.         while (b != 0) {
  12.             int temp = b;
  13.             b = a % b;
  14.             a = temp;
  15.         }
  16.         return a;
  17.     }
  18.  
  19.     public static void main(String[] args) {
  20.  
  21.         int[] arr = {5, 12, 8, 21, 3, 17, 9, 14, 6, 25};
  22.         int n = arr.length;
  23.  
  24.         List<Integer> chainSizes = new ArrayList<>();
  25.  
  26.         boolean[] visited = new boolean[n];
  27.  
  28.         for (int start = 0; start < n; start++) {
  29.  
  30.             if (visited[start]) continue;
  31.  
  32.             int size = 1;
  33.             visited[start] = true;
  34.  
  35.             int current = start;
  36.  
  37.             while (true) {
  38.                 int next = (current + 1) % n;
  39.  
  40.                 if (visited[next]) break;
  41.  
  42.                 if (gcd(arr[current], arr[next]) > 1) {
  43.                     size++;
  44.                     visited[next] = true;
  45.                     current = next;
  46.                 } else {
  47.                     break;
  48.                 }
  49.             }
  50.  
  51.             if (size > 1) {
  52.                 chainSizes.add(size);
  53.             }
  54.         }
  55.  
  56.         int sum = 0;
  57.         for(int k = 2; k <= n; k++){
  58.         	for(int i = 0; i < chainSizes.size(); i++){
  59.         	sum += chainSizes.get(i) / (k-1);
  60.         	}
  61.         }
  62.         System.out.print(sum);
  63. 	}
  64. }
Success #stdin #stdout 0.08s 54612KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9
https://ideone.com/5pqfHV
language:
Java (HotSpot 12)
created:
1 day 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!