import sys
import math
import bisect
from collections import defaultdict

def sieve(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.isqrt(n)) + 1):
        if sieve[i]:
            sieve[i*i : n+1 : i] = [False] * len(sieve[i*i : n+1 : i])
    primes = [i for i, is_prime in enumerate(sieve) if is_prime]
    return primes

primes = sieve(44721)
prime_squares = [p * p for p in primes]
prime_squares.sort()

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

freq = defaultdict(int)
total = 0

for x in a:
    low = x + 1
    high = x + 10**9

    left = bisect.bisect_left(prime_squares, low)
    right = bisect.bisect_right(prime_squares, high)

    for s in prime_squares[left:right]:
        y = s - x
        total += freq.get(y, 0)
    
    freq[x] += 1

print(total)