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 Prime_Numbers_Check(x):
    i=2
    flag=True
    while i <= math.sqrt(x):
        if x%i==0:
            flag=False  
            break
        i+=1
    return flag
def Prime_Numbers_Count(A):
    sum=0
    for i in A:
        if Prime_Numbers_Check(i):
            sum+=1
    return sum

if __name__ == "__main__":
    A=[]
    n=int(input())
    for i in range(n):
        A.append(int(input()))
    sum=Prime_Numbers_Count(A)
    print(sum)

Solution (Python):
import math
n=int(input())
A=[0]*n
cnt=0
for i in range(0,n):
    A[i]=int(input())
for i in range(0,n):
    if A[i]<2: pass
    elif A[i]==2 or A[i]==3 or A[i]==5 or A[i]==7:
        cnt+=1
    else:
        x=int(math.sqrt(A[i])+1)
        for j in range(2,x):
            if A[i]%j==0:
                break
            else: pass
            if j==x-1:
                cnt+=1
            else: pass
print(cnt)

Solution (Python):
import math

n=int(input())
A=[0 for i in range(n)]
cnt=0
for i in range(n):
    A[i]=int(input())
for i in range(n):
    a=int(math.sqrt(A[i])+1)
    if A[i]<2: pass
    elif A[i]==2 or A[i]==3 or A[i]==5 or A[i]==7:
        cnt+=1
    else:
        for j in range(2,a):
            if A[i]%j==0:
                break
            if j==a-1:
                cnt+=1
print(cnt)

Solution (Python):

import math

n=int(input())

sum=0

for i in range(n):
	b=1
	n=int(input())
	for j in range(2,int(math.sqrt(n))+1):
		if n%j==0:
			b=0
			break
	sum+=b
			
print(sum)

Solution (Python):
import math
def PrimeNum(a):
	x=math.sqrt(a)
	x=int(x)
	tmp=1
	if a==1:
		tmp=0
	elif a==2:
		tmp==1
	elif a>3 and a<9:
		for i in range(2,a):
			st=a%i
			if st==0:
				tmp=0
				break
	
	else:
		for i in range(2,x+1):
			st=a%i
			if st == 0:
				tmp=0
				break
	
		
	

	return tmp	
	
n=int(input())
p=[]
att=0
for i in range(n):
	p.append(int(input()))
	att+=PrimeNum(p[i])
	
print(att)

Solution (Python):
import math

cou = 0
n = int(input())
A = [int(input()) for i in range(n)]

for i in range(n):
    a_sq = int(math.sqrt(A[i]))
    for j in range(2,a_sq+2):
        if(A[i]%j==0 and not(A[i]==j)):
            break
        if(j==a_sq+1):
            cou += 1

print(cou)

Solution (Python):
import math
def s(x):
    r=0
    s=math.sqrt(x)
    s=(int)(s)
    for i in range(2,s+1):
        w=x%i
        if w==0:
            r=r+1
    return r
N=int(input())
A=[0 for i in range(N)]
for i in range(N):
    A[i]=int(input())
t=0
i=2
for i in range(N):
    r=s(A[i])
    if r==0:
        t=t+1
print(t)

Solution (Python):
import math

N=int(input())

A=[0 for i in range(N)]
for i in range(N):
	A[i]=int(input())

c=0 
cnt=0

for k in range(N):
	x=math.sqrt(A[k])
	x=(int)(x)
	for j in range(2,x+1):
		if A[k]%j==0:
			cnt+=1
			break
	if cnt==0:
		c+=1
	
	cnt=0


print(c)

Solution (Python):
import math
n=int(input())
a=[]

for i in range(n):
  a.append(input())
cnt=0
b=[int(i) for i in a]

for i in range(n):
    c=math.sqrt(b[i])
    c=int(c)
    if b[i]==2:
      cnt+=1
    for j in range(2,b[i]):
      if b[i]%j==0:
        break
      if math.sqrt(b[i])<j:
        cnt+=1
        break
print(cnt)

Solution (Python):

import math

n = int(input())
c = 0
for i in range(n):
    x = int(input())
    f = 1
    for j in range(2,int(math.sqrt(x))+1):
        if x % j == 0: 
            f = 0
            break
    c = c + f
print(c)

Solution (Python):
import math
def jud(s):
    for i in range(2,int(math.sqrt(s))+1):
            if s%i == 0:
                return 0
    return 1

n = int(input())
a = [0]*n
cnt = 0

for i in range(n):
    a[i] = int(input())
    han = jud(a[i])
    if han == 1:
        cnt += 1

print(cnt)

Solution (Python):
import math
def jud(s):
    for i in range(2,int(math.sqrt(s))+1):
            if s%i == 0:
                return 0
    return 1

n = int(input())
a = [0]*n
cnt = 0

for i in range(n):
    a[i] = int(input())
    han = jud(a[i])
    if han == 1:
        cnt += 1

print(cnt)

Solution (Python):
import math

def s(x):
    r=0
    s=math.sqrt(x)
    s=(int)(s)

    for i in range(2,s+1):
        w=x%i
        if w==0:
            r=r+1
    return r

N=int(input())
A=[0 for i in range(N)]
for i in range(N):
    A[i]=int(input())

t=0
i=2
for i in range(N):
    r=s(A[i])
    if r==0:
        t=t+1
print(t)

Solution (Python):

import math as mh
a=int(input())
A=[0]*a
x=0
for i in range(a):
 A[i]=int(input())
 for j in range(1,A[i]):
  if A[i]==2:
    x+=1
    continue
  if j==1:
   continue
  elif (A[i]%j)==0:
   break
  elif j>=mh.sqrt(A[i]):
   x+=1
   break
print(x)

Solution (Python):
import math

def is_prime(n):
	for i in range(2,math.floor(math.sqrt(n))+1):
		if n%i==0:
			return False
	return True
 
cnt = 0
n=int(input())
for i in range(n):
    k=int(input())
    if is_prime(k):
        cnt+=1
print(cnt)

Solution (Python):



import math

def is_prime_number(x):
    if x < 2: return False
    elif x == 2: return True
    elif x%2 == 0: return False

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

    return True

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

print(prime_num)

Solution (Python):
import math
n=int(input())
R=[0]*n
sum=0
for i in range(n):
    R[i]=int(input())
for i in range(n):
    if R[i]<0:
        continue
    s=math.sqrt(R[i])
    s=int(s)+1
    for j in range(2,s+1):
        if R[i]==j:
            sum=sum+1
        if R[i]%j==0:
            break
        if j==s:
            sum=sum+1
print(sum)

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

p = []   
pc = [True for _ in range(10001)]
pc[0] = False
pc[1] = False

for i in range(2,10001):
    if pc[i]:
        
        p.append(i)
        for j in range(i,10001,i):
            pc[j] = False

cnt = 0
for i in a:
    if i<=10000:
        if i in p:
            cnt += 1
    else:
        isp = True
        for j in p:
            if i%j == 0:
                isp = False
                break
        if isp:
            cnt += 1

print(cnt)

Solution (Python):
import sys
input()
print(sum(1 for x in map(int,sys.stdin)if 2 in[x,pow(2,x,x)]))

Solution (Python):
import sys
input()
print(sum(1 for x in map(int,sys.stdin)if 2 in[x,pow(2,x,x)]))

Solution (Python):
import sys
input()
def f():print(sum(2 in[x,pow(2,x,x)]for x in map(int,sys.stdin)))
f()

Solution (Python):
import sys
input()
def f():print(sum(2 in[x,pow(2,x,x)]for x in map(int,sys.stdin)))
f()

Solution (Python):
import sys
input()
print(sum(2 in[x,pow(2,x,x)]for x in map(int,sys.stdin.readlines())))

Solution (Python):
import sys
input()
print(sum(2 in[x,pow(2,x,x)]for x in map(int,sys.stdin.readlines())))

Solution (Python):
import sys
input()
def s():print(sum(2 in[x,pow(2,x,x)]for x in map(int,sys.stdin.readlines())))
if'__main__'==__name__:s()

Solution (Python):
import sys
input()
def s():print(sum(2 in[x,pow(2,x,x)]for x in map(int,sys.stdin.readlines())))
if'__main__'==__name__:s()

Solution (Python):
n = int(input())

li = [int(input()) for i in range(n)]

ans = 0
for a in li:
    flag = True
    for i in range(2, int(a**0.5)+1):
        if a % i == 0:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
import math
def is_prime(x):
    if x == 1 or x == 2:
        return True

    for idx in range(2, int(math.sqrt(x))+1):
        if x % idx == 0:
            return False

    return True

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

    print(cnt)

main()

Solution (Python):


import math


def Isprime(num):
    for j in range(2, int(math.sqrt(num)) + 1):
        if num % j == 0:
            return 0
    return 1


count = 0
n = int(input())
for i in range(n):
    num = int(input())
    count += Isprime(num)

print(count)

Solution (Python):
import math

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


if __name__ == '__main__':
    n = int(input())
    prime_numbers = []

    for i in range(n):
        num = int(input())
        if is_prime(num):
            prime_numbers.append(num)

    print(len(prime_numbers))

Solution (Python):
n = int(input())
nums = [int(input()) for i in range(n)]
prime_num = 0

def prime(n):
    q = abs(n)
    if q==2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


for i in nums:
    if(prime(i)):
        prime_num += 1

print(prime_num)

Solution (Python):
import sys
import math


n = input()
num = [int(i) for i in sys.stdin.readlines()]
count = 0

for i in num:
    if i == 1:
        continue
    elif i == 2:
        
        count += 1
        continue

    square = int(math.sqrt(i))

    for j in range(2, square+1):
        if i % j == 0:
            break
    else:
        
        count += 1

print(count)

Solution (Python):
import math

def prime_numbers(numbers):
    return list(map(is_prime, numbers)).count(True)


def is_prime(n):
    if (n == 2):
        return True
    elif (n % 2 == 0):
        return False
    else:
        i = 3
        while i <= math.sqrt(n):
            if n % i == 0:
                return False
            i += 2

    return True

if __name__ == '__main__':
    n = int(input())
    numbers = []
    for i in range(0, n):
        numbers.append(int(input()))
    print(prime_numbers(numbers))

Solution (Python):
n=int(input())
c=0
for i in range(n):
    p=int(input())
    if pow(2,p-1,p)==1 or p==2:
        c+=1
print(c)

Solution (Python):

from math import sqrt, floor

def intinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def get_prime():
    P = []
    P.append(2); P.append(3); P.append(5); P.append(7)
    
    
    for n in range(8, 101):
        is_prime = True
        for i in range(4):
            if n % P[i] == 0: is_prime = False; break
        if is_prime: P.append(n)
    for n in range(101, 10001):
        is_prime = True
        limit = floor(sqrt(n))
        for i in range(len(P)):
            if n % P[i] == 0: is_prime = False; break
            if P[i] > limit: break
        if is_prime: P.append(n)
    return P

def main():
    
    
    primes = get_prime()
    n = int(input())
    data = []
    for i in range(n): data.append(int(input()))
    count = 0
    for i in range(n):
        
        if data[i] == 1: continue
        if data[i] == 2: count += 1; continue
        
        limit = floor(sqrt(data[i]))
        is_prime = True
        for p in primes:
            if data[i] % p == 0: is_prime = False; break
            if p > limit: break
        if is_prime: count += 1
    print(count)

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
a = []

count = 0
for i in range(N):
    x=int(input())
    if x == 2:
        count+=1
    else:
        if pow(2, x-1,x ) == 1:
            count+=1
        else:
            pass

print(count)

Solution (Python):
import math


def count_number_of_prime_number(v):
    ans = 0
    for x in v:
        if is_prime(x):
            ans += 1
    return ans


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


n = int(input())
v = []
for i in range(n):
    v.append(int(input()))

print(count_number_of_prime_number(v))

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

cnt = 0
for i in range(int(input())):
    n = int(input())
    if n == 2:
        cnt += 1
        continue
    elif n % 2 == 0: continue
    judge = prime()
    if judge == True:
        cnt += 1
print(cnt)

Solution (Python):
from sys import stdin
def stdinput():
    return stdin.readline().strip()

def main():
    n = int(stdinput())
    inputs = list(map(int, [stdinput() for _ in range(n)]))

    primes = 0
    for a in inputs:
        if is_prime(a, None):
            primes += 1
    print(primes)

def is_prime(a, primes):
    
    
    
    for p in range(2, int(a ** 0.5)  + 1):
        if a % p == 0:
            return False
    return True

if __name__ == '__main__':
    main()

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

n = int(input())
ans = 0
for i in range(n):
    ans += is_prime(int(input()))
print(ans)

Solution (Python):
def eratos(n):
	is_prime = [True for i in range(n+1)]
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, n+1):
		if i * i > n:
			break
		for j in range(i*i, n+1, i):
			is_prime[j] = False
	return is_prime

is_prime = eratos(10000)
primes = []
for i in range(10001):
    if is_prime[i] is True:
        primes.append(i)

n = int(input())
ans = 0
for _ in range(n):
    x = int(input())
    if x <= 10000:
        if is_prime[x] is True:
            ans += 1
    else:
        ok = True
        for i in primes:
            if i * i > x:
                break
            if x % i == 0:
                ok = False
                break
        if ok is True:
            ans += 1
    
print(ans)

Solution (Python):
import math

def is_prime(num):
	if num <= 1: return False
	if num == 2: return True
	if num % 2 == 0: return False
	for i in range(3, int(math.sqrt(num)) + 1):
		if num % i == 0: return False
	return True

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

Solution (Python):
import math

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

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

Solution (Python):
import math
n = int(input())
c = 0
for x in range(n):
    a = int(input())
    for b in range(2, int(math.sqrt(a))+1):
        if a % b == 0:
            break
    else:
        c += 1
print(c)

Solution (Python):
def is_prime(num):
	if num <= 1: return False
	if num == 2: return True
	if num % 2 == 0: return False
	i = 3
	while i <= num**0.5:
		if num % i == 0: return False
		i += 2
	return True
	
n = int(input())
cnt = 0
for i in range(n):
	if is_prime(int(input())):
		cnt += 1
print(cnt)

Solution (Python):
import math


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


N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))

Solution (Python):
import math


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


N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))

Solution (Python):
import math

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

N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))

Solution (Python):
import math

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

N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))

Solution (Python):
import math

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

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

    return True

N = input()
N = int(N)
l = [input() for i in range(N)]
a = 0
for i in range(0,len(l)):
    if is_prime(int(l[i])) == True:
         a += 1
print(a)

Solution (Python):
import math

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

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

    return True

N = input()
N = int(N)
l = [input() for i in range(N)]
a = 0
for i in range(0,len(l)):
    if is_prime(int(l[i])) == True:
         a += 1
print(a)

Solution (Python):
import math

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

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

    return True

N = input()
N = int(N)
l = [int(input()) for i in range(N)]
a = 0
for i in range(0,len(l)):
    if is_prime(l[i]) == True:
         a += 1
print(a)

Solution (Python):
def is_prime(a):
    if a == 1:
        return False
    for i in range(2, a):
        if a % i == 0:
            return False
        if i * i > a:
            break
    return True

n = int(input())
ans = 0
for i in range(n):
    a = int(input())
    if is_prime(a):
        ans += 1
print(ans)

Solution (Python):
def function(a):
    for j in range(2,a):
        if a%j==0:
            return 1
        if j**2>a:
            break
    return 0
n=int(input())
s=0
for i in range(n):
    a=int(input())
    s+=function(a)
print(n-s)

Solution (Python):
import math

def is_prime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    for i in range(2, math.ceil(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def run():
    n = int(input())
    n_prime = 0
    for i in range(n):
        if is_prime(int(input())):
            n_prime += 1
    print(n_prime)

if __name__ == '__main__':
    run()

Solution (Python):


n = int(input())

def isPrime(a):
    
    if a == 2:
        return True
    elif a < 2 or a % 2 == 0:
        return False
    else:
        i = 3
        j = a ** 0.5
        while i <= j:
            if a % i == 0:
                return False
            i += 2
        return True

primeCount = 0
for i in range(n):
    a = int(input())
    if isPrime(a) == True:
        
        primeCount += 1

print(primeCount)

Solution (Python):
n = int(input())
mlist = []
plist = [2]
for i in range(3,10000):
    count = 0
    for k in plist:
        if (i%k != 0):
            count += 1
        else:
            break
    if (count == len(plist)):
        plist.append(i)
def check(m):
    for p in plist:
        if (m <= p):
            return True
        if m%p == 0:
            return False
    return True
count = 0
for i in range(n):
    m = int(input())
    if check(m):
        count += 1
        
print(count)

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

n = int(input())
xs = []
for i in range(n):
    x = int(input())
    xs.append(x)

print(sum(1 for x in xs if isprime(x)))

Solution (Python):
class PrimeChecker:

    def __init__(self):
        self.primes = [2,3]

    def isPrime(self, n):
        if n in self.primes:
            return True
        else:
            for i in self.primes:
                if n % i == 0:
                    return False

        i = 5
        w = 2

        while i * i <= n:
            if n % i == 0:
                return False

            i += w
            w = 6 - w

        self.primes.append(n)

        return True

primeChecker = PrimeChecker()
count = 0
N = int(input())
for _ in range(N):
    if primeChecker.isPrime((int(input()))):
        count += 1
print(count)

Solution (Python):
class PrimeChecker:

    def __init__(self):
        self.primes = [2,3]

    def isPrime(self, n):
        if n in self.primes:
            return True
        else:
            for i in self.primes:
                if n % i == 0:
                    return False

        i = 5
        w = 2

        while i * i <= n:
            if n % i == 0:
                return False

            i += w
            w = 6 - w

        self.primes.append(n)

        return True

primeChecker = PrimeChecker()
count = 0
N = int(input())
for _ in range(N):
    if primeChecker.isPrime((int(input()))):
        count += 1
print(count)

Solution (Python):
class PrimeChecker:
 
    def __init__(self):
        self.primes = [2,3,5]
 
    def isPrime(self, n):
        if n in self.primes:
            return True
        elif n < self.primes[-1]:
            return False
        else:
            for i in self.primes:
                if n % i == 0:
                    return False
 
        i = self.primes[-1]
        w = 2 if i % 6 == 5 else 4
 
        while i * i <= n:
            if self.isPrime(i):
                self.primes.append(i) 
                if n % i == 0:
                    return False
 
            i += w
            w = 6 - w
 
        return True
 
primeChecker = PrimeChecker()
count = 0
N = int(input())
for _ in range(N):
    if primeChecker.isPrime((int(input()))):
        count += 1
print(count)

Solution (Python):
class PrimeChecker:
 
    def __init__(self):
        self.primes = [2,3,5]
 
    def isPrime(self, n):
        if n in self.primes:
            return True
        elif n < self.primes[-1]:
            return False
        else:
            for i in self.primes:
                if n % i == 0:
                    return False
 
        i = self.primes[-1]
        w = 2 if i % 6 == 5 else 4
 
        while i * i <= n:
            if self.isPrime(i):
                self.primes.append(i) 
                if n % i == 0:
                    return False
 
            i += w
            w = 6 - w
 
        return True
 
primeChecker = PrimeChecker()
count = 0
N = int(input())
for _ in range(N):
    if primeChecker.isPrime((int(input()))):
        count += 1
print(count)

Solution (Python):
f=lambda x: 1 if x==2 or x==3 or (not x<2 and not x&1==0 and pow(2,x-1,x)==1) else 0
print(sum(f(int(input())) for _ in range(int(input()))))

Solution (Python):
import math

def main():
    N = input()
    n = [input() for x in range(N)]
    c = 0

    for i in range(N):
        if prime(n[i]):
            c += 1

    print(c)

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

main()

Solution (Python):
def get_primes(n):
    if n < 10: return [2,3,5,7]
    x = [0,0]+[i for i in range(2,n+1)]
    for e in get_primes(int(n**0.5+1)):
        for j in range(e*2, n+1,e):
            x[j] = 0
    return filter(None, x)

PRIMES = get_primes(10000)
n = int(input())
c = 0
for i in range(n):
    p = int(input())
    f = 1
    for e in PRIMES:
        if e >= p:
            break
        if p % e == 0:
            f = 0
            break
    c += f
print c

Solution (Python):
def get_primes(n):
    x = [0,0]+[i for i in range(2,n+1)]
    for i in range(int(n**0.5+1)):
        e = x[i]
        if e !=0:
            for j in range(e*2, n+1,e):
                x[j] = 0
    return filter(None, x)

PRIMES = get_primes(10000)
n = int(input())
c = 0
for i in range(n):
    p = int(input())
    f = 1
    for e in PRIMES:
        if e >= p:
            break
        if p % e == 0:
            f = 0
            break
    c += f
print c

Solution (Python):
def get_primes(n):
    x = [0,0]+[i for i in range(2,n+1)]
    for i in range(int(n**0.5+1)):
        e = x[i]
        if e !=0:
            for j in range(e*2, n+1,e):
                x[j] = 0
    return filter(None, x)

PRIMES = get_primes(10000)
n = int(input())
c = 0
for i in range(n):
    p = int(input())
    f = 1
    for e in PRIMES:
        if e >= p:
            break
        if p % e == 0:
            f = 0
            break
    c += f
print c

Solution (Python):
import random
def is_prime(q,k=50):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in xrange(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n=input()
ans=0
for i in range(n):
    p=input()
    if is_prime(p):
        ans+=1
print ans

Solution (Python):

from __future__ import division, print_function
from sys import stdin
from math import sqrt
n = int(stdin.readline())
cnt = 0
for _ in range(n):
    v = int(stdin.readline())
    if v == 2:
        cnt += 1
    elif v % 2 == 1:
        for i in xrange(3, int(sqrt(v))+1, 2):
            if v % i == 0:
                break
        else:
            cnt += 1
print(cnt)

Solution (Python):



import time
import sys
import io
import re
import math
start = time.clock()
cnt=0

N=int(raw_input())
for j in range(N):
    x=int(raw_input())
    if x<2: pass

    elif x==2: cnt+=1
    elif x%2==1:
        for i in xrange(3, int(x**0.5)+1, 2):
            if x%i==0:
                break
        else:
            cnt+=1
print cnt

Solution (Python):
n = input()
s = 0
while n > 0:
	n -= 1
	a = input()
	if a == 1:
		pass
	elif a == 2:
		s += 1
	elif (a%2 == 1):
		for i in xrange(3, (int(a**0.5)+1), 2):
			if a%i==0:
				break	
		else:
			s += 1		
print s

Solution (Python):
def main():
    N = int(raw_input())
    s = [int(raw_input()) for x in range(N)]
    count = 0
    for i in s:
        if is_prime(i):
            count +=1
    print count
    
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

main()

Solution (Python):
import math
def prime2(x):
    if x == 2: return True
    else:
        for s in stock:
            if x % s == 0: return False
        for j in xrange(3,int(math.sqrt(x))+1,2):
            if x % j == 0: return False
        else:
            stock.append(x)
            return True 
n = input()
count = 0
stock = [2]
for i in xrange(n):
    if prime2(input()): count += 1
print count

Solution (Python):
import math
def prime(x):
    if x == 2: return True
    elif x % 2 == 0: return False
    else:
        for j in xrange(3,int(math.sqrt(x))+1,2):
            if x % j == 0: return False
        else:
            return True 
n = input()
count = 0
for i in xrange(n):
    if prime(input()): count += 1
print count

Solution (Python):
def isPrime(p):
	if p == 2: return 1
	if p < 2 or p&1 == 0: return 0
	return 1 if pow(2,p-1,p) == 1 else 0
	
n = int(raw_input())
print sum(isPrime(int(raw_input())) for i in range(n))

Solution (Python):
def isPrime(p):
	if p == 2: return 1
	if p < 2 or p&1 == 0: return 0
	return 1 if pow(2,p-1,p) == 1 else 0
	
n = int(raw_input())
print sum(isPrime(int(raw_input())) for i in range(n))

Solution (Python):
import math

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

if __name__ == "__main__":
    import sys
    N = int(sys.stdin.readline().strip())
    ret = 0
    for i in range(N):
        if isPrime(int(sys.stdin.readline().strip())):
            ret += 1
    print ret

Solution (Python):
import math

def isprime(x):
    if x == 2: return True
    if x % 2 == 0: return False
    for i in range(3, math.ceil(math.sqrt(x)) + 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):
import random

def miller_rabin_test(n,k): 
    d = n-1
    r = 0
    while True:
        if d%2 == 0:
            r += 1
            d //= 2
        else:
            break
    
    for i in range(k):
        a = random.randint(2,n-2)
        x = pow(a,d,n)
        if x == 1 or x == n-1:
            continue
        flag = False
        for j in range(r-1):
            x = pow(x,2,n)
            if x == n-1:
                flag = True
                break
            if x == 1:
                break
        if flag:
            continue
        else:
            return False
        
    return True

n = int(input())
a = [int(input()) for _ in range(n)]

count = 0
for i in range(n):
    if a[i] == 2 or a[i] == 3:
        count += 1
        continue
    if a[i] <= 3 or a[i]%2==0:
        continue
    if miller_rabin_test(a[i],100):
        count += 1
print(count)

Solution (Python):
times = int(input())
count = 0
import math

def isPrime(x):
    d = 3
    if x == 2:
        return True
    if x%2 == 0:
        return False
    while d <= math.sqrt(x):
        if x%d == 0:
            return False
        d += 2
    return True
    
for i in range(times):
    num = int(input())
    if isPrime(num) == True:
        count += 1

print(count)

Solution (Python):
n = int(input())
ls = []
counter = 0
for i in range(n):
	ls.append(int(input()))
for k in ls:
	s = 2
	ms = k
	if k == 2:
		counter += 1
	else:
		while ms >= s:
			if k % s == 0:
				break
			ms = k // s + 1
			s += 1
		else:
			counter += 1
print(counter)

Solution (Python):
def is_prime(x):
    if x == 1:
        return False
    for d in range(2, int(x ** 0.5)+1):
        if x % d == 0:
            return False
    return True


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

Solution (Python):
n=int(input())
a=[int(input()) for i in range(n)]
count=0
def isprime(x):
    A=0
    for i in range(2,int(x**(0.5))+1):
        if x%i==0:
            A=1
            break
    if A==0:
        return True
    else:
        return False
for i in a:
    if isprime(i)==True:
        count+=1
print(count)

Solution (Python):
import math

def isprime(n):
    if n==1:return False
    
    for k in range(2,int(math.floor(math.sqrt(n)))+1):
        if n%k==0:
            return False
            
    return True
    
n=int(input())
a=0

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

Solution (Python):
import math

def Sosu(N) :
    for i in range(2, int(math.sqrt(N))+1) :
        if N % i == 0 :
            return 'F'
    return 'T'
    

n = int(input())
ans = 0
for j in range(n) :
    a = int(input())
    if Sosu(a) == 'T' :
        ans += 1

print(ans)

Solution (Python):
import math
def isprime(N):
    if N==2:
        return True
    elif N<=1 or N%2==0:
        return False
    l = int(math.sqrt(N))
    for i in range(3,l+1,2):
        if N % i == 0:
            return False
        i += 2
    return True

N = int(input())
ans = 0
for i in range(N):
    ans += int(isprime(int(input())))
print(ans)

Solution (Python):
N = int(input())
a = 0

for _ in range(N):
  n = int(input())
  i = 2
  while i * i <= n:
    if n % i == 0:
      break
    i += 1
  else:
    a += 1

print(a)