fork download
copy 
  1. public class CoprimeNeighbors {
  2. 	long gcd(long a, long b) {
  3. 		return a == 0 ? b : gcd(b % a, a);
  4. 	}
  5. 	final long BIL = 1000 * 1000 * 1000;
  6. 	boolean isPrime(int a) {
  7. 		for(int i = 2; i * i <= a; ++i)
  8. 			if(a % i == 0)
  9. 				return false;
  10. 		return true;
  11. 	}
  12. 	// find first 'cnt' primes
  13. 	int[] findPrimes(int cnt) {
  14. 		int[] primes = new int[cnt];
  15. 		int next = 2;
  16. 		for(int i = 0; i < cnt; ++i) {
  17. 			while(!isPrime(next))
  18. 				++next;
  19. 			primes[i] = next++;
  20. 		}
  21. 		return primes;
  22. 	}
  23. 	// return product of 'k' random primes
  24. 	static Random rand = new Random();
  25. 	long randomNumber(int[] primes, boolean[] forbidden, int k) {
  26. 		int n = primes.length;
  27. 		boolean[] taken = new boolean[n];
  28. 		long x = 1;
  29. 		for(int repeat = 0; repeat < k; ++repeat) {
  30. 			int i;
  31. 			do {
  32. 				i = rand.nextInt(n);
  33. 			} while(taken[i] || forbidden[i]);
  34. 			taken[i] = true;
  35. 			long product = x * primes[i];
  36. 			if(product / primes[i] != x || product > BIL * BIL) {
  37. 				System.out.println("exceed");
  38. 				return randomNumber(primes, forbidden, k); // 1e18 exceeded, try again
  39. 			}
  40. 			x *= primes[i];
  41. 		}
  42. 		return x;
  43. 	}
  44. 	public long[] findAny(int len) {
  45. 		final int x = 32, y = 11;
  46. 		long[] t = new long[len];
  47. 		int[] primes = findPrimes(x);
  48. 		System.out.println(Arrays.toString(primes));
  49. 		for(int i = 0; i < len; ++i) {
  50. 			boolean[] forbidden = new boolean[x];
  51. 			if(i != 0)
  52. 				for(int j = 0; j < x; ++j)
  53. 					if(t[i-1] % primes[j] == 0)
  54. 						forbidden[j] = true;
  55. 			while(true) {
  56. 				t[i] = randomNumber(primes, forbidden, y);
  57. 				boolean ok = true;
  58. 				for(int j = 0; j < i - 1; ++j)
  59. 					if(gcd(t[j], t[i]) == 1)
  60. 						ok = false;
  61. 				if(ok) break;
  62. 				System.out.println("gcd");
  63. 			}
  64. 		}
  65. 		return t;
  66. 	}
  67. }
  68.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:7: error: class CoprimeNeighbors is public, should be declared in a file named CoprimeNeighbors.java
public class CoprimeNeighbors {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/3Ek3zb
language:
Java (12.0.1)
created:
7 years 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!