Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Prime Team

By skmonir · Limits 1s, 512 MB

There are n players standing in a line. Each of the players is assigned a unique jersey number. You have to form as many team as possible satisfying the following rules.
1. Each team will contain two players. One of them will lead the team.
2. The jersey number of the leader must be a prime number.

You are given the jersey number of each player. Find the maximum number teams can be formed without violating the rules.

Input

First line of the input contains an integer n(1 ≤ n ≤ 100) — The number of players.
Second line contains n space-separated integers a1, a2,…, an (1 ≤ ai ≤ 1000), where ai denotes the jersey number of the ith player.

Output

Print an integer k — the maximum number teams that can be formed without violating the rules.

Sample

InputOutput
7
1 9 4 3 8 5 2
3

One possible way to form 3 teams is:
Team-1 → 1st and 4th player, jersey number [1, 3]
Team-2 → 2nd and 6th player, jersey number [9, 5]
Team-3 → 3rd and 7th player, jersey number [4, 2]


Discussion

Statistics


81% Solution Ratio

fuadulhasanEarliest, 4w ago

fuadulhasanFastest, 0.0s

fuadulhasanLightest, 131 kB

mdvirusShortest, 248B

Submit

Login to submit