public class CoprimeNeighbors { long gcd(long a, long b) { return a == 0 ? b : gcd(b % a, a); } final long BIL = 1000 * 1000 * 1000; boolean isPrime(int a) { for(int i = 2; i * i <= a; ++i) if(a % i == 0) return false; return true; } // find first 'cnt' primes int[] findPrimes(int cnt) { int[] primes = new int[cnt]; int next = 2; for(int i = 0; i < cnt; ++i) { while(!isPrime(next)) ++next; primes[i] = next++; } return primes; } // return product of 'k' random primes static Random rand = new Random(); long randomNumber(int[] primes, boolean[] forbidden, int k) { int n = primes.length; boolean[] taken = new boolean[n]; long x = 1; for(int repeat = 0; repeat < k; ++repeat) { int i; do { i = rand.nextInt(n); } while(taken[i] || forbidden[i]); taken[i] = true; long product = x * primes[i]; if(product / primes[i] != x || product > BIL * BIL) { System.out.println("exceed"); return randomNumber(primes, forbidden, k); // 1e18 exceeded, try again } x *= primes[i]; } return x; } public long[] findAny(int len) { final int x = 32, y = 11; long[] t = new long[len]; int[] primes = findPrimes(x); System.out.println(Arrays.toString(primes)); for(int i = 0; i < len; ++i) { boolean[] forbidden = new boolean[x]; if(i != 0) for(int j = 0; j < x; ++j) if(t[i-1] % primes[j] == 0) forbidden[j] = true; while(true) { t[i] = randomNumber(primes, forbidden, y); boolean ok = true; for(int j = 0; j < i - 1; ++j) if(gcd(t[j], t[i]) == 1) ok = false; if(ok) break; System.out.println("gcd"); } } return t; } }