fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4. import java.math.*;
  5.  
  6. class Ideone
  7. {
  8. 	public static void main (String[] args) throws java.lang.Exception
  9. 	{
  10. 		int[] primes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
  11. 						47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
  12. 						101, 103, 107, 109, 113, 127, 131, 137, 139,
  13. 						149, 151, 157, 163, 167, 173, 179, 181, 191};
  14. 		// precompute inverses and bounds
  15. 		BigInteger[] inverses = new BigInteger[primes.length];
  16. 		BigInteger[] bounds = new BigInteger[primes.length];
  17. 		BigInteger m = BigInteger.ZERO.setBit(1344);
  18. 		for (int i = 0; i < primes.length; i++) {
  19. 			BigInteger p = BigInteger.valueOf(primes[i]);
  20. 			inverses[i] = p.modInverse(m);
  21. 			bounds[i] = m.divide(p);
  22. 		}
  23.  
  24. 		m = m.subtract(BigInteger.ONE);
  25. 		BigInteger x = BigInteger.ZERO.setBit(1330)
  26. 			.subtract(BigInteger.ONE);
  27. 		for (int i = 0; i < primes.length; i++) {
  28. 			isMultipleOf(x, inverses[i], bounds[i], m);
  29. 			x.remainder(BigInteger.valueOf(primes[i]));
  30. 		}
  31.  
  32. 		long t1 = System.currentTimeMillis();
  33. 		for (int j = 0; j < 100; j++)
  34. 		for (int i = 0; i < primes.length; i++) {
  35. 			if (isMultipleOf(x, inverses[i], bounds[i], m))
  36. 				ignore = true;
  37. 		}
  38. 		long t2 = System.currentTimeMillis();
  39. 		for (int j = 0; j < 100; j++)
  40. 		for (int i = 0; i < primes.length; i++) {
  41. 			if (x.remainder(BigInteger.valueOf(primes[i])).equals(BigInteger.ZERO))
  42. 				ignore = true;
  43. 		}
  44. 		long t3 = System.currentTimeMillis();
  45. 		System.out.println("Using inverses: " + (t2 - t1) + " using remainder: " + (t3 - t2));
  46.  
  47. 		for (int i = 0; i < primes.length; i++) {
  48. 			if (isMultipleOf(x, inverses[i], bounds[i], m))
  49. 				System.out.print(primes[i] + ", ");
  50. 		}
  51. 		System.out.println();
  52. 	}
  53.  
  54. 	static volatile boolean ignore;
  55.  
  56. 	static boolean isMultipleOf(BigInteger value, BigInteger inverse, BigInteger bound, BigInteger m) {
  57. 		return value.multiply(inverse).and(m).compareTo(bound) <= 0;
  58. 	}
  59. }
Success #stdin #stdout 0.22s 43880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Using inverses: 75 using remainder: 17
3, 11, 31, 43, 71, 127, 191,
https://ideone.com/5Gqarc
language:
Java (HotSpot 12)
created:
6 years 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!