SHARE
TWEET

Untitled

a guest Jan 12th, 2017 132 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.             int n = in.nextInt();
  2.             int[] s = new int[n];
  3.             int max = -1;
  4.             for (int i = 0; i < n; ++i) {
  5.                 s[i] = in.nextInt();
  6.                 max = Math.max(max, s[i]);
  7.             }
  8.             List<Integer> primes = new ArrayList<>();
  9.             boolean[] prime = new boolean[max + 1];
  10.             Arrays.fill(prime, true);
  11.             prime[0] = prime[1] = false;
  12.             int[] p = new int[max + 1];
  13.             int ind = 0;
  14.             for (int i = 2; i <= max; ++i) {
  15.                 if (prime[i]) {
  16.                     if ((long)i * i <= max) {
  17.                         for (int j = i * i; j <= max; j += i) {
  18.                             prime[j] = false;
  19.                         }
  20.                     }
  21.                     p[ind++] = i;
  22.                 }
  23.             }
  24.             int ans = 0;
  25.             for (int i = 0; i < ind; ++i) {
  26.                 int temp = 0;
  27.                 for (int j = 0; j < n && p[i] <= s[j]; ++j) {
  28.                     if (factorization(s[j], p[i])) {
  29.                         ++temp;
  30.                     }
  31.                 }
  32.                 ans = Math.max(ans, temp);
  33.             }
  34.             out.println(Math.max(ans, 1));
  35.         }
  36.         static boolean factorization(int n, int t) {
  37.             int z = 2;
  38.             while (z * z <= n) {
  39.                 if (n % z == 0) {
  40.                     n /= z;
  41.                     if (z == t) {
  42.                         return true;
  43.                     }
  44.                 } else {
  45.                     z++;
  46.                 }
  47.             }
  48.             if (n > 1) {
  49.                 return n == t;
  50.             }
  51.             return false;
  52.         }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top