Problem:
Prime Numbers A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5 and 7. Write a program which reads a list of N integers and prints the number of prime numbers in the list. Input The first line contains an integer N , the number of elements in the list.  N numbers are given in the following lines. Output Print the number of prime numbers in the given list. Constraints 1 ≤ N ≤ 10000 2 ≤ an element of the list ≤ 10 8  Sample Input 1 5
2
3
4
5
6 Sample Output 1 3 Sample Input 2 11
7
8
9
10
11
12
13
14
15
16
17 Sample Output 2 4

Solution (Python):
import math
def isPrime(n):
    if n <= 1:
        return False
    elif n < 4:
        return True
    elif n % 2 == 0:
        return False
    elif n < 9:
        return True
    elif n % 3 == 0:
        return False
    else:
        i = 5
        while i <= math.sqrt(n):
            if n % i == 0:
                return False
            if n % (i + 2) == 0:
                return False
            i+=6
    return True
            
N = int(raw_input())
D = [int(raw_input()) for i in xrange(N)]
count = 0
for i in D:
    if isPrime(i) == True:
        count += 1
print count

Solution (Python):
import math

def prime(a):
	if a==1:
		return 0
	n=2
	while n<=math.sqrt(a):
		if a%n==0:
			return 0
		n+=1
	return 1

N=int(input())

count=0
for i in range(N):
	a=int(input())
	count+=prime(a)
print(count)

Solution (Python):
import math

def isPrime( x ):
	if 2 == x or 3 == x:
		return True
	if 0 == x&1:
		return False
	i = 3
	limit = math.sqrt( x )
	while  i <= limit:
		if 0 == x%i:
			return False
		i += 2
	return True
 
 
n = int( raw_input( ) )
nums = []
i = 0
while i < n:
    nums.append( int( raw_input( ) ) )
    i += 1
cnt = i = 0
for val in nums:
    if isPrime( val ):
        cnt += 1
 
print( cnt )

Solution (Python):
import math

def isPrime( x ):
	if 2 == x or 3 == x:
		return True
	if 0 == x&1:
		return False
	i = 3
	limit = math.sqrt( x )
	while  i <= limit:
		if 0 == x%i:
			return False
		i += 2
	return True
 
 
n = int( input( ) )
nums = []
i = 0
while i < n:
    nums.append( int( input( ) ) )
    i += 1
cnt = i = 0
for val in nums:
    if isPrime( val ):
        cnt += 1
 
print( cnt )

Solution (Python):
import pdb

n = int(raw_input())
count = 0
for x in xrange(n):
  target = int(raw_input())
  
  if target == 2:
    count += 1
  elif target < 3 or not target & 1:
    continue
  else:
    if pow(2, target - 1, target) == 1:
      count += 1

print count

Solution (Python):
import sys
import math

count = 0
judge = 0

for line in sys.stdin.readlines():
    num = int(line.strip())
    if judge == 0:
        judge = 1
    else:    
        flag = 0
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                flag = 1
                break
        if flag == 0:
            count += 1

print count

Solution (Python):
import sys
import math

count = 0

num_list = []

for line in sys.stdin.readlines():
    num_list.append(int(line.strip()))

num_list.remove(num_list[0])

for num in num_list:
        flag = 0
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                flag = 1
                break
        if flag == 0:
            count += 1

print count

Solution (Python):
import math

def isprime(x):
        if x == 2:
                return True
        if x < 2 or x % 2 == 0:
                return False
        i = 3
        while(i <= math.sqrt(x)):
                if x % i == 0:
                        return False
                i += 2

        return True

num = raw_input()

count = 0
for i in range(int(num)):
        x = raw_input()
        if isprime(int(x)):
                count += 1

print count

Solution (Python):
import sys
import math

x_list = []

for line in sys.stdin.readlines():
  x_list.append(int(line.strip()))

count = 0

x_list.remove(x_list[0])

for i in x_list:
  flag = 0
  for j in range(2, int(math.sqrt(i))+1):
    if i % j == 0:
      flag = 1
      break
  if flag == 0:
    count += 1

print count

Solution (Python):
import math

def isPrime(x):
    if(x == 1 ):
        return False

    n = int(math.sqrt(x))

    for i in range(2,n+1):
        if(x % i == 0):
            return False
    return True

n = int(input())
dataset = []
while (n > 0):
     dataset.append(int(input()))
     n -=1

prime_number = 0
for x in dataset:
    if(isPrime(x)):
        prime_number += 1

print(prime_number)

Solution (Python):
import math

n = int(raw_input())
num = list()
count = 0
max = 0

for i in range(n):
    num.append(int(raw_input()))

for i in range(n):
    root_num = math.sqrt(num[i])
    for j in range(2, int(root_num) + 1):
        if num[i] % j == 0:
            count = count + 1
            break

print n - count

Solution (Python):
import math

n = int(raw_input())
num = list()
count = 0
max = 0

for i in range(n):
    num.append(int(raw_input()))

for i in range(n):
    root_num = math.sqrt(num[i])
    for j in range(2, int(root_num) + 1):
        if num[i] % j == 0:
            count = count + 1
            break

print n - count

Solution (Python):
import math


def IsPrime(x):
    i=2
    while(i<=math.sqrt(x)):
        if(x%i==0):
            return False
        i+=1
    return True

a=[]
n=int(input())
nn=n
i=0
while(n>i):
    b=int(input())
    if(not IsPrime(b)):
        nn-=1
    i+=1
print(nn)

Solution (Python):
import math

num = raw_input()
num_list = []
for i in range(int(num)):
    a = raw_input()
    num_list.append(int(a))
count = 0

for num in num_list:
    if num <= 1:
        continue
    elif num == 2:
        count += 1
    elif num % 2 == 0:
        continue
    else:
        count += 1
        for i in range(3, int(math.sqrt(num))+1, 2):
            if num % i == 0:
                count -= 1
                break
print count

Solution (Python):
import math

numbers = []
n = raw_input()
for i in range(int(n)):
    input_num = raw_input()
    numbers.append(int(input_num))

count = 0
for num in numbers:
    prime_frag = True
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            prime_frag = False
            break
    if prime_frag:
        count += 1
print count

Solution (Python):
N = int(input())
ns = [int(input()) for _ in range(N)]




















def is_prime(n):
  if n < 2: return False
  if n == 2: return True
  if n % 2 == 0: return False

  d = 3
  while d ** 2 <= n:
    if n % d == 0:
      return False
    d += 2
  return True

print(len([n for n in ns if is_prime(n)]))

Solution (Python):
import math
N = input()
pnum_count = N
for _ in range(N):
    n = input()
    if n == 2:
        continue
    if n % 2 == 0:
        pnum_count -= 1
        continue
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            pnum_count -= 1
            break
        i += 1
print pnum_count

Solution (Python):
import math
Num = input()
N = [input() for _ in range(Num)]
pnum_count = Num
for n in N:
    if n == 2:
        continue
    if n % 2 == 0:
        pnum_count -= 1
        continue
    i = 2
    while i <= math.sqrt(n):
        if n % i == 0:
            pnum_count -= 1
            break
        i += 1
print pnum_count

Solution (Python):
import math
def prime_array(n=1000):
	List = [2]
	i = 3
	while i <= n:
		judge = True
		for k in List :
			if math.sqrt(i) < k :
				break
			if i%k == 0:
				judge = False
				break
		if judge :
			List.append(i)
		i += 2
	return List
def main():
	cnt=0
	prime_List=prime_array(10**4)
	n=input()
	for i in range(n):
		a=input()
		if a<=10**4:
			for j in prime_List:
				if a==j:
					cnt+=1
					break
		else:
			judge=True
			for j in prime_List:
				if a%j==0:
					judge=False
					break
			if judge:
				cnt+=1
	print('%d' % cnt)
if __name__=='__main__':
	main()

Solution (Python):



import math


def isprime(n):
    if n == 2:
        return True
    elif n < 2 or n % 2 == 0:
        return False
    else:
        for i in range(3, math.floor(math.sqrt(n)) + 1, 2):
            if n % i == 0:
                return False
        else:
            return True


def main():
    n = int(input())
    ms = (int(input()) for i in range(n))
    print(len(list(filter(isprime, ms))))

if __name__ == "__main__":
    main()

Solution (Python):
import math

def isprime(n):
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    for i in range(3, math.floor(math.sqrt(n))+1 , 2):
        if x % i == 0:
            return False
    return True

n = int(input())
count = 0
for i in range(n):
    x = int(input())
    if isprime(x):
        count += 1
print(count)

Solution (Python):
from math import sqrt
N = input()
sum = 0
for _ in xrange(N):
    n = input()
    for i in xrange(2,int(sqrt(n))+1):
        if n%i == 0:
            break
    else:
        sum += 1
print sum

Solution (Python):
N = input()
sum = 0
for _ in xrange(N):
    n = input()
    for i in xrange(2,n):
        if i > n/i:
            sum += 1
            break
        if n%i == 0:
            break
    else:
        sum += 1
print sum

Solution (Python):
n = int(raw_input())
a = []
for i in range(n):
    a.append(int(raw_input()))

nprimes = 0
a = sorted(a)
while True:
    for d in range(2,10001):
        if d**2>a[0]:
            nprimes+=1
            del a[0]
            break
        elif a[0]%d==0:
            del a[0]
            break
    if len(a) <= 0:
        break

print nprimes

Solution (Python):
N = int(input())
n = [int(input()) for i in range(N)]

def Is_prime(n):
    if n == 2:
        return True
    if n == 1:
        return False
    if n % 2 == 0:
        return False
    i = 3
    while i < int(n ** (0.5))+ 1:
        if n % i == 0:
            return False
        i += 2
    return True

count = 0
for j in n:
    if Is_prime(j):
        count += 1

print (count)

Solution (Python):
def is_prime(n):
    
    if n == 2:
        return True
    elif n < 2 or n & 1 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

N = int(input())
cnt = 0
for i in range(N):
    e = int(input())
    if is_prime(e):
        cnt += 1
print(cnt)

Solution (Python):
from math import sqrt, floor


def is_prime(p):
    for i in range(2, floor(sqrt(p)) + 1):
        if not p % i:
            return False
    return True


n = int(input())
print(sum(is_prime(int(input())) for _ in range(n)))

Solution (Python):
import math

def is_prime(x):
    if x == 2:
        return True

    if x % 2 == 0 or x < 2:
        return False

    i = 3
    x_sqrt = math.sqrt(x)
    while i <= x_sqrt:
        if x % i == 0:
            return False
        i += 2

    return True

if __name__ == "__main__":
    n = int(input())
    count = 0
    for i in range(n):
        if is_prime(int(input())):
            count += 1

    print(count)

Solution (Python):
def is_prime(x):
    if x == 2:
        return True
    
    if x < 2 or x % 2 == 0:
        return False

    for i in range(3, int(x**0.5)+1, 2):
        if x % i == 0:
            return False
    
    return True


N = int(input())
cnt = 0
for _ in range(N):
    i = int(input())
    cnt += is_prime(i)
print(cnt)

Solution (Python):
def is_prime(x):
    if x <= 1:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

cnt = 0
for _ in range(int(input())):
    if is_prime(int(input())):
        cnt += 1
print(cnt)

Solution (Python):
import math
n = int(raw_input())
N = []
for i in xrange(n):
    N.append(int(raw_input()))

def isPrime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False

    i = 3
    while i <= math.sqrt(x):
        if x % i == 0:
            return False
        i += 2

    return True

def main():
    cnt = 0
    for x in N:
        if isPrime(x):
            cnt += 1
    print cnt

    return 0

main()

Solution (Python):
import math
n = int(raw_input())
N = [int(raw_input()) for _ in xrange(n)]

def isPrime(x):
    if x == 2:
        return True

    if x < 2 or x % 2 == 0:
        return False

    i = 3
    while i <= math.sqrt(x):
        if x % i == 0:
            return False
        i += 2

    return True

def main():
    cnt = 0
    for x in N:
        if isPrime(x):
            cnt += 1
    print cnt
    return 0

main()

Solution (Python):
import math

def checkPrime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

if __name__ == "__main__":
    N = input()
    cnt = 0
    for i in range(N):
        n = input()
        if checkPrime(n):
            cnt += 1
    print cnt

Solution (Python):

 
import sys
num = []
ans = []
def prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


for i in sys.stdin:
    inp = map(int , i.split())
    if prime(inp[0]):
        num.append(inp)
num.sort()

for i in xrange(1, len(num)):
    if num[i - 1] != num[i]:
        ans.append(num[i][0])
print len(ans) + 1

Solution (Python):
a=input()
def ip(a):
    i=2
    while i**2<=a:
        if a%i==0:return False
        i+=1
    return True
b=0
for i in range(int(a)):
    c=input()
    if ip(int(c)):b+=1
print(str(b))

Solution (Python):
c = 0
while True:
    try:
        n = int(input())
    except EOFError:
        break
    c += 1
    for i in range(2, int(n ** 0.5 + 1)):
        if n % i == 0:
            c -= 1
            break
print(c)

Solution (Python):

c = 0
for i in range(int(input())):
    n = int(input())
    for i in range(2, int(n ** 0.5 + 1)):
        if n % i == 0:
            break
    else:
        c += 1
print(c)

Solution (Python):
c = 0
for i in range(int(input())):
    n = int(input())
    for i in range(2, int(n ** 0.5 + 1)):
        if n % i == 0:
            break
    else:
        c += 1
print(c)

Solution (Python):
c = 0
for i in range(int(input())):
    n = int(input())
    for i in range(2, int(n ** 0.5 + 1)):
        if n % i == 0:
            break
    else:
        c += 1
print(c)

Solution (Python):



def is_prime(num):
    if num==2 or num==3:
        return True
    for x in xrange(2,int(num**0.5)+1):
        if num%x ==0:
            return False
    return True

count = 0
for i in xrange(input()):
    input_prime_candidate = input()
    if is_prime(input_prime_candidate):
        count+=1
print count

Solution (Python):
import math

def isPrime(x):
	if x == 2:
		return True

	if x < 2 or x % 2 == 0:
		return False

	i = 3
	while i <= math.sqrt(x):
		if x % i == 0:
			return False
		i = i + 2

	return True

if __name__ == '__main__':
	n = int(input())
	A = [int(input()) for i in range(n)]

	cnt = 0
	for i in range(n):
		if isPrime(A[i]) == True:
			cnt = cnt + 1

	print(cnt)

Solution (Python):


def isPrime(p):
    if p == 2:
        return True
    elif p < 2 or p%2 == 0:
        return False
    elif pow(2, p-1, p) == 1:
        return True
    else:
        return False

n = int(raw_input())
count = 0
for i in range(n):
    if isPrime(int(raw_input())):
        count += 1
print count

Solution (Python):
import math
A = []
N = int(input())
count = 0
for n in range(N):
    x = int(input())
    if x == 2:
        A.append(x)
        count += 1
    elif x % 2 == 0:
        pass
    elif x > 2:
        for i in range(3, int(math.sqrt(x))+2, 2):
            if x % i == 0:
                break
        else:
            count += 1
            A.append(x)
    
print(count)

Solution (Python):
def isPrime(x):
    if x==2:
        return True
    if x<2 or x%2==0:
        return False
    if pow(2,x-1,x)==1:
        return True
    else:
        return False

n=input()
ct=0
for i in xrange(n):
    if isPrime(input()):
        ct+=1
print(ct)

Solution (Python):
import math


def is_prime(n):
    global primes
    if n == 1:
        return False

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    s = int(math.sqrt(n))
    for x in range(3, s + 1, 2):
        if n % x == 0:
            return False
    else:
        return True


N = int(input())
d = [int(input()) for _ in range(N)]
d.sort()
print([is_prime(x) for x in d].count(True))

Solution (Python):
import math
 
 
def is_prime(n):
    global primes
    if n == 1:
        return False
 
    if n == 2:
        return True
 
    if n % 2 == 0:
        return False
 
    s = int(math.sqrt(n))
    for x in range(3, s + 1, 2):
        if n % x == 0:
            return False
    else:
        return True
 
 
N = int(input())
d = [int(input()) for _ in range(N)]
print([is_prime(x) for x in d].count(True))

Solution (Python):
from random import randrange

def eratosthenes(size):
    table = [True] * (size + 1)
    table[0] = table[1] = True
    for i in range(2, int(round(pow(size+1, 0.5)))):
        if not table[i]:
            continue
        for j in range(i + i, size+1, i):
            table[j] = False
    return table

def miller_rabin(n, k=20):
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    d = n - 1
    while d & 1 == 0:
        d >>= 1
    for _ in range(k):
        a = randrange(1, n)
        y = pow(a, d, n)
        t = d
        while (t != n - 1) and (y != 1) and (y != n - 1):
            y = pow(y, 2, n)
            t <<= 1
        if (y != n - 1 ) and ((t & 1) == 0):
            return False
    return True

if __name__ == "__main__":
    N = int(input())
    print(sum(map(miller_rabin, [int(input()) for _ in range(N)])))

Solution (Python):
from random import randrange


def eratosthenes(size):
    table = [True] * (size + 1)
    table[0] = table[1] = True
    for i in range(2, int(round(pow(size+1, 0.5)))):
        if not table[i]:
            continue
        for j in range(i + i, size+1, i):
            table[j] = False
    return table


def miller_rabin(n, k=20):
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    d = n - 1
    while d & 1 == 0:
        d >>= 1
    for _ in range(k):
        a = randrange(1, n)
        y = pow(a, d, n)
        t = d
        while t != n - 1 and y != 1 and y != n - 1:
            y = pow(y, 2, n)
            t <<= 1
        if y != n - 1 and (t & 1) == 0:
            return False
    return True

if __name__ == "__main__":
    N = int(input())
    print(sum(map(miller_rabin, [int(input()) for _ in range(N)])))

Solution (Python):
def isPrime(num):
    if num == 2: return 1
    if num < 2 or num&1 == 0: return 0
    if pow(2, num-1, num) == 1: return 1
    return 0

n = input()
s = 0
for i in xrange(n):
    s += isPrime(input())

print s

Solution (Python):
def is_prime(x):
    if x == 2:
        return True
    if x < 2 or x%2==0:
        return False
    i = 3
    while i <= x**(0.5):
        if x%i==0:
            return False
        i+=2
    return True

if __name__=='__main__':
    N=int(input())
    cnt=0
    for _ in range(N):
        if is_prime(int(input())): cnt+=1
    print(cnt)

Solution (Python):
def judge(int):
    if int == 2:return 1
    elif int <= 1 :return 0
    i = 2
    while i*i <= int:
        if int % i == 0:return 0 
        i += 1
    return 1



n = input()
count = 0
for i in range(n):
    if judge(input()) == 1:
        count+=1
print count

Solution (Python):
import sys
import math

def str_input():
    S = raw_input()
    if S[len(S)-1] == "\r":
        return S[:len(S)-1]
    return S

def float_to_str(num):
    return str("{:.10f}".format(num))

def list_input(tp):
    return map(tp, str_input().split())



n = input()

cnt = 0

for i in xrange(n):
    m = input()
    for j in xrange(2, int(math.sqrt(m))+1):
        if m % j == 0:
            break
    else:
        cnt += 1

print cnt

Solution (Python):


import math

num = int(input())

result = 0

while num > 0:
	x = int(input())
	isPrime = 0
	if x == 2:
		isPrime = 1
	elif x < 2 or x % 2 == 0:
		pass
	else:
		i = 3
		isPrime2 = 1
		while i <= math.sqrt(x):
			if x % i == 0:
				isPrime2 = 0
				break
			i = i + 2
		if isPrime2:
			isPrime = 1
	if isPrime:
		result += 1
	num -= 1

print(result)

Solution (Python):
def composite(d,n,s):
    for a in (2,3,5,7):
        probably_prime = False
        if pow(a,d,n) == 1:
            continue
        for i in range(s):
            if pow(a, 2**i * d, n) == n-1:
                probably_prime = True
                break
        return not probably_prime
    return False

def is_prime(n):
    if n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        d,s = n-1, 0
        while not d%2:
            d, s = d>>1, s+1
        return not composite(d,n,s)

r = []
n = int(input())
for i in range(n):
  n = int(input())
  if is_prime(n):
      if n not in r:
          r.append(n)

print(len(r))

Solution (Python):
def composite(d,n,s):
    for a in (2,3,5,7):
        maybe_prime = False
        if pow(a,d,n) == 1:
            maybe_prime = True
            continue
        for i in range(s):
            if pow(a, 2**i * d, n) == n-1:
                maybe_prime = True
                break
        return not maybe_prime
    return False

def is_prime(n):
    if n==2:
        return True
    elif n%2==0:
        return False
    else:
        d,s = n-1, 0
        while not d%2:
            d,s = d>>1,s+1
        return not composite(d,n,s)
r = []
n = int(input())
for i in range(n):
  n = int(input())
  if is_prime(n):
      if n not in r:
          r.append(n)

print(len(r))

Solution (Python):
def composite(d,n,s):
    for a in (2,3,5,7):
        p = False
        if pow(a,d,n) == 1:
            p = True
            continue
        for i in range(s):
            if pow(a, 2**i * d, n) == n-1:
                p = True
                break
        return not p
    return False

def is_prime(n):
    if n==2:
        return True
    elif n%2==0:
        return False
    else:
        d,s = n-1, 0
        while not d%2:
            d,s = d>>1,s+1
        return not composite(d,n,s)
r = []
n = int(input())
for i in range(n):
  n = int(input())
  if is_prime(n):
      if n not in r:
          r.append(n)

print(len(r))

Solution (Python):
def composite(d,n,s):
    for a in (2,3,5,7):
        p = False
        if pow(a,d,n) == 1:
            continue
        for i in range(s):
            if pow(a, 2**i * d, n) == n-1:
                p = True
                break
        if not p:
            return True
    return False

def is_prime(n):
    if n in (2,3,5,7):
        return True
    elif 0 in (n%2,n%3,n%5,n%7):
        return False
    else:
        d,s = n-1, 0
        while not d%2:
            d,s = d>>1,s+1
        return not composite(d,n,s)
r = []
n = int(input())
for i in range(n):
  n = int(input())
  if is_prime(n):
      if n not in r:
          r.append(n)

print(len(r))

Solution (Python):
def isPrime(n):
    if n==2 or n==3:
        return True
    elif n%2==0:
        return False
    else:
        i = 2
        while i**2 <= n:
            if n%i == 0:
                return False
            i += 1
    return True
    
r = []
n = int(input())
for i in range(n):
    p = int(input())
    if isPrime(p):
        if p not in r:
            r.append(p)

print(len(r))

Solution (Python):

N=int(raw_input())
s=[int(raw_input()) for x in range(N)]


def is_prime(n):
  i = 2
  while i * i <=n:
    if n % i == 0:
      return False
    i += 1
  return True

a=filter(is_prime,s)
print len(a)

Solution (Python):
def composite(d,n,s):
    for a in (2,3,5,7):
        p = False
        if pow(a,d,n) == 1:
            continue
        for i in range(s):
            if pow(a, 2**i * d, n) == n-1:
                p = True
                break
        if not p:
            return True
    return False
 
def is_prime(n):
    if n in (2,3,5,7):
        return True
    elif 0 in (n%2,n%3,n%5,n%7):
        return False
    else:
        d,s = n-1, 0
        while not d%2:
            d,s = d>>1,s+1
        return not composite(d,n,s)
r = []
n = int(input())
for i in range(n):
  n = int(input())
  if is_prime(n):
    r.append(n)
 
print(len(r))

Solution (Python):
def composite(d,n,s):
    for a in (2,3,5,7):
        p = False
        if pow(a,d,n) == 1:
            continue
        for i in range(s):
            if pow(a, 2**i * d, n) == n-1:
                p = True
                break
        if not p:
            return True
    return False
  
def is_prime(n):
    if n in (2,3,5,7):
        return True
    else:
        d,s = n-1, 0
        while not d%2:
            d,s = d>>1,s+1
        return not composite(d,n,s)
r = []
n = int(input())
for i in range(n):
  n = int(input())
  if is_prime(n):
    r.append(n)
  
print(len(r))

Solution (Python):



def is_prime(number):
    if number == 2:
        return True
    elif number < 2 or number % 2 == 0:
        return False
    else:
        i = 3
        while i <= pow(number, 0.5):
            if number % i == 0:
                return False
            i += 2
        return True


if __name__ == '__main__':
    N = input()
    numbers = [input() for i in xrange(N)]
    count = 0
    for i in xrange(len(numbers)):
        if is_prime(numbers[i]):
            count += 1
    print count

Solution (Python):
import sys
import math


prime_numbers = [2, 3, 5, 7]

def prime_numbers_under(num):
  global prime_numbers

  prime_number_max = max(prime_numbers)
  if prime_number_max > num:
    return prime_numbers

  for i in range(prime_number_max + 1, num + 1):
    check_max = math.floor(math.sqrt(i))
    for j in prime_numbers:
      if j <= check_max:
        if i % j == 0:
          break
    else:
      prime_numbers.append(i)

  return prime_numbers

def main():
  amount = 0

  length = int(input())
  for _ in range(0, length):
    i = int(input())
    check_max = math.floor(math.sqrt(i))
    for j in prime_numbers_under(check_max):
      if j <= check_max:
        if i % j == 0:
          break
    else:
      amount += 1

  print(amount)
  return 0


if __name__ == '__main__':
  main()

Solution (Python):
import math
def isprime(x):
  if x == 2:
    return True

  if x < 2 or x % 2 == 0:
    return False

  i = 3
  while i <= math.sqrt(x):
    if x % i == 0:
      return False
    i = i + 2

  return True


count = 0
n = int(input())
for i in range(0, n):
  if isprime(int(input())):
    count += 1

print(count)

Solution (Python):
import math


def is_prime(n):
  if n in [2, 3, 5, 7]:
    return True
  elif 0 in [n%2, n%3, n%5, n%7]:
    return False
  else:
    check_max = math.ceil(math.sqrt(n))
    for i in range(2, check_max + 1):
      if n % i == 0:
        return False
    else:
      return True

def main():
  primes = set([])
  length = int(input())
  for _ in range(0, length):
    n = int(input())
    if is_prime(n):
      primes.add(n)

  print(len(primes))
  return 0


if __name__ == '__main__':
  main()

Solution (Python):
def prime(num):
    if num == 0:
        return False
    elif num == 1:
        return False
    elif num == 2:
        return True
    i = 2
    while True:
        if i**2 > num:
            break
        if num%i==0:
            return False
        i += 1
    return True
n = int(raw_input())

nums = []
for _ in range(n):
    a = int(raw_input())
    nums.append(a)

ret = 0
for num in nums:
    if prime(num):
        ret += 1
print ret

Solution (Python):
def is_prime(x):
    if x == 2:
        return True
    if (x < 2) or (x%2 == 0):
        return False
    return all(x%i for i in xrange(3, int(x**(0.5) + 1), 2))

N = input()
print sum(is_prime(input()) for i in range(N))

Solution (Python):
def prime_numbers(n):
    cnds = [True] * n
    for x in xrange(2, int(n**0.5 + 1)):
        if cnds[x]:
            for m in xrange(2*x, n, x):
                cnds[m] = False
    return [i for i in xrange(2, n) if cnds[i]]

def is_prime(n):
    return all(n % m for m in primes if m < n)

primes = prime_numbers(10**4)
N = input()
print sum(is_prime(input()) for i in range(N))

Solution (Python):
from math import sqrt
def prime(n):
    if n == 2:
        return True
    elif n < 2 or n % 2 == 0:
        return False
    else:
        i = 3
        while i <= sqrt(n):
            if n % i == 0:
                return False
            i += 2
    return True

n = int(input())
c = 0
for i in range(n):
    if(prime(int(input()))):
        c += 1

print(c)

Solution (Python):


def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1
    
ans = 0
n = int(input())
for i in range(n):
    if is_prime(int(input())):
        ans += 1
    
print(ans)

Solution (Python):
import math

def is_prime(num):
    i = 2
    while i <= math.sqrt(num):
        if num % i == 0:
            return False
        i = i + 1
    return True

N = int(input())
cnt = 0
for i in range(0, N):
    n = int(input())
    if (is_prime(n)):
        cnt = cnt + 1
        
print(cnt)

Solution (Python):
def is_prime(num):
    i = 2
    while i*i <= num:
        if num % i == 0:
            return False
        i = i + 1
    return True

N = int(input())
cnt = 0
for i in range(0, N):
    n = int(input())
    if (is_prime(n)):
        cnt = cnt + 1
        
print(cnt)

Solution (Python):
import math
primenum =int(input())
ans = 0
for p in range(primenum):
    targ = int(input())
    for t in range(2,math.floor(math.sqrt(targ)) + 1):
        if targ % t == 0:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
def isPrime(n):
    i = 2
    while i*i <= n:
        if n % i == 0:
            return False
        i += 1
    return True
    
n = int(input())
ans = 0

for i in range(n):
    t = int(input())
    if isPrime(t):
        ans += 1
print(ans)

Solution (Python):
import sys,math

def is_prime_number(arg):
    arg_sqrt=int(math.floor(math.sqrt(arg)))
    i=2
    while i <=arg_sqrt:
        if arg %i ==0:
            return False
        i+=1

    return True
        
        
n=0
prime_numbers=0
for line in sys.stdin:
    l=int(line)
    if n == 0:
        n=l
        continue

    if is_prime_number(l):
        prime_numbers+=1
        

print prime_numbers

Solution (Python):
import math
def is_prime(x):
    if x == 2:
        return True
    if (x % 2 == 0):
        return False
    m = math.ceil(math.sqrt(x))
    for i in range(3, m + 1):
        if x % i == 0:
            return False
    return True


n = int(input())

prime = 0
for i in range(n):
    x = int(input())
    if is_prime(x):
        prime += 1

print(prime)

Solution (Python):
import sys
import math

def is_prime_number(num):
    if num == 2:
        return True
    
    if num == 1 or num % 2 == 0:
        return False

    max_cnt = int(math.sqrt(num))
    if max_cnt % 2 == 0:
        max_cnt -= 1
        
    for i in range(max_cnt, 2, -2):
        if num % i == 0:
            return False

    return True

def main():
    n = int(sys.stdin.readline().strip())
    sum = 0
    for _ in range(n):
        num = int(sys.stdin.readline().strip())
        if is_prime_number(num):
            sum += 1

    print(sum)

if __name__ == '__main__':
    main()

Solution (Python):
def getprimes(n):
  primes = []
  for i in xrange(2, n+1):
    isprime = True
    for j in xrange(len(primes)):
      if i % primes[j] == 0:
        isprime = False
        break
    if isprime:
      primes.append(i)
  return primes

n = int(raw_input())
primes = getprimes(10000)
count = 0
for _ in xrange(n):
  x = int(raw_input())
  isprime = True
  for i in xrange(len(primes)):
    if primes[i] >= x:
      break
    if x % primes[i] == 0:
      isprime = False
      break
  if isprime:
    count += 1
print count