#include <bits/stdc++.h>
using namespace std;
int memo[100000001];
int dp[100000001];
int main() {
  int N;
  cin >> N;
  memo[0] = true;
  memo[1] = true;
  int im = sqrt(100000000) + 1;
  for (int i = 2; i <= im; i += 2) {
    if (!memo[i]) {
      for (int j = i * i; j <= 100000000; j += i) {
        memo[j] = true;
      }
    }
  }
  for (int i = 2; i <= im; i++) {
    if (!memo[i])
      dp[i] = dp[i - 1] + 1;
    else
      dp[i] = dp[i - 1];
  }
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    ans = max(ans, dp[x]);
  }
  cout << ans << endl;
}
