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 boolean solve(long number) {
  11. 		for (long prime : primes) {
  12. 			long x = number % prime; // x < prime < 10^9
  13. 			long v = ((5 * x * x) + (2 * x) + (1)) % prime;
  14. 			if (!isPerfectSquare(v, prime)) {
  15. 				return false;
  16. 			}
  17. 		}
  18. 		return true;
  19. 	}
  20.  
  21. 	static boolean isPerfectSquare(long num, long prime) {
  22. 		return pow(num, (prime - 1) / 2, prime) <= 1;
  23. 	}
  24.  
  25. 	static long pow(long a, long b, long mod) {
  26. 		long c = 1;
  27. 		for (; b > 0; b /= 2) {
  28. 			if (b % 2 == 1) {
  29. 				c = (c * a) % mod;
  30. 			}
  31. 			a = (a * a) % mod;
  32. 		}
  33. 		return c;
  34. 	}
  35.  
  36. 	static long[] primes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
  37. 							53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
  38. 							109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
  39. 							173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
  40. 							233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
  41. 							293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359};
  42.  
  43. 	public static void main (String[] args) throws java.lang.Exception
  44. 	{
  45. 		System.out.println(solve(1_576_239));
  46. 	}
  47. }
Success #stdin #stdout 0.04s 711168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
https://ideone.com/kxB3zE
language:
Java (HotSpot 12)
created:
8 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!