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(p):
    if p==2 or p==3:
        return True
    else:
        i = int(math.sqrt(p))
        while i>=2:
            if p%i==0:
                return False
                break
            i-=1
        return True
                
            

N = int(input())
count = 0

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

Solution (Python):
N = int(input())
a = [int(input()) for x in range(N)]

import math

cnt = 0
for i in range(N) :
    cnt += 1
    if a[i] == 2 :
        continue
    else :
        for j in range(2, int(math.sqrt(a[i])) + 1) :
            if a[i] % 2 == 0 :
                cnt -= 1
                break
            if a[i] % j == 0 :
                cnt -= 1
                break
            
print(cnt)

Solution (Python):
n = int(input())
ls = [int(input()) for _ in range(n)]


def judge(n):
    if n == 2 or n == 3:
        return 1
    if n % 2 == 0:
        return 0
    i = 3
    while i <= n/i:
        if n%i == 0:
            return 0
        else:  
            i += 2
    return 1

print(sum(map(judge, ls)))

Solution (Python):
import math
n = int(input())
count = 0
for i in range(n):
    t = int(input())
    a = int(t ** (1 / 2))
    end = 0
    for j in range(2, a + 1):
        if t % j == 0:
            end = 1
            break
    if end == 0:
        count += 1
print(count)

Solution (Python):
def primeq(x):
    if x==1:return False
    for i in range(2,int(x**.5)+1):
        if x%i==0:return False
    return True

c=0
for i in range(int(input())):
    if primeq(int(input())):c+=1
print(c)

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 main():
    n = int(input())
    count = 0
    for _ in range(n):
        x = int(input())
        count += isprime(x)
    print(count)

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

if __name__ == '__main__':
    main()

Solution (Python):
import math

def isPrime(num):
    for i in range(int(math.sqrt(num)), 1, -1):
        if num % i == 0:
            return None
    return num

inputs = []

while True:
    try:
        inputs.append(input())
    except(EOFError):
        break

inputs.pop(0)

print(len([x for x in list(map(isPrime, map(int, inputs))) if x is not None]))

Solution (Python):
n = int(input())
sum = 0
for _ in range(n):
    a = int(input())
    if a == 2:
        continue
    for i in range(a):
        x = i + 2
        if a%x == 0:
            sum += 1
            break
        if x > a ** 0.5:
            break
print(n - sum)

Solution (Python):
import math
n = input()
prime_count = 0
is_prime = 1

for i in range(0,n):
	is_prime = 1
	prime_check_number = input()
	if prime_check_number == 2:
		prime_count = prime_count + 1
		continue
	elif prime_check_number == 1 or prime_check_number % 2 == 0:
		continue
	else:
		prime_check_number_sqrt = int(math.sqrt(prime_check_number))
		for j in range(3,prime_check_number_sqrt+1,2):
			if prime_check_number % j == 0:
				is_prime = 0
				break

	if is_prime == 1:
		prime_count = prime_count + 1

print(prime_count)

Solution (Python):
import math

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

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

Solution (Python):
import math
n = int(raw_input())
cnt = 0
for i in range(n):
    j = 2
    num = int(raw_input())
    while j <= math.sqrt(num):
        if num % j == 0:
            break
        j+=1
    if j > math.sqrt(num):
        cnt+=1
print cnt

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

Solution (Python):
print(sum(map(lambda x: 1 if x == 2 or pow(2,x-1,x) == 1 else 0, [int(input()) for _ in range(int(input()))])))

Solution (Python):
import math
import cmath
def check(inp):
    if inp==2:
        return True
    for num in xrange(2,int(math.sqrt(inp)+1)):
        if inp%num==0:
            return False
    return True
st=set()


while True:
    try:
       str=raw_input().strip()

    except EOFError:
        break
    
    num=int(str)
    st.add(num)
sum=0
for nm in st:
    if check(nm):
        sum+=1
print sum

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 ** .5) + 1, 2):
        if x % i == 0:
            return False
    return True
n = int(input())
print(sum(is_prime(int(input())) for _ in range(n)))

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

    return True

L = []
while True:
    try:
        i = int(input())
        L.append(i)
    except EOFError:
        break
K = 0
for i in range(len(L)):
    if prime(L[i]):
        K += 1

print(K)

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

n = int(input())
ans = 0

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

Solution (Python):
import math
def isprime(n):
    if n==1:
        return False
    elif n==2:
        return True
    k=int(math.sqrt(n))+1
    for i in range(2,k+1):
        if n%i==0:
            return False
    return True
N=int(input())
ans=0
for i in range(N):
    if isprime(int(input())):
        ans+=1
print(ans)

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

count = 0
for i in range(0, x):
    a =  int(input())
    for j in range ( 2,  a ):
        c = int(a)
        if a % j == 0:
            count += 1
            break;
        if j * j  > c:
            break;
        
print(x-count)

Solution (Python):
import math
def prime(num):
    judge = True
    for i in range(2, int(math.sqrt(num)+1)):
        if num % i == 0:
            judge = False
    return judge
    
n = int(input())
cnt = 0
ns=[]
for i in range(n):
    num = int(input())
    if prime(num):
        cnt += 1
print(cnt)

Solution (Python):
import math
def prime(num):
    judge = True
    for i in range(2, int(math.sqrt(num)+1)):
        if num % i == 0:
            judge = False
    return judge
    
n = int(input())
cnt = 0
a =[]
for i in range(n):
    num = int(input())
    if prime(num):
        cnt += 1
print(cnt)

Solution (Python):
def isprime(n):
    check = 1
    if n == 2:
        pass
    elif n == 1 or n % 2 == 0:
        check = 0
    else:
        i = 3
        while i * i <= n:
            if n % i == 0:
                check = 0
                break
            else:
                i += 2
    return check
        

n = int(input())
ans = 0
for k in range(n):
    a = int(input())
    ans += isprime(a)
    
print(ans)

Solution (Python):
"""素数を求める。

以下の性質を用いる。
合成数 x は p <= sqrt(x) を満たす素因子 pをもつ。
"""

import math


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


N = int(input())
data = [int(input()) for i in range(N)]
cnt = 0
for d in data:
    if is_prime(d):
        cnt += 1
print(cnt)

Solution (Python):
def is_prime(n):
    i=2
    while i*i<=n:
        if n%i==0:
            return False
        i+=1
    return True
    
s=[]
for _ in range(int(input())):
    s.append(is_prime(int(input())))
print(sum(s))

Solution (Python):
def isPrime(n):
    for i in range(2, n):
        if i * i > n:
            return 1
        if n % i == 0:
            return 0
    return 1
 
ans = 0
n = int(input())
for i in range(n):
    x = int(input())
    ans = ans + isPrime(x)
 
print(ans)

Solution (Python):
import math

def is_prime(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return n != 1

n = int(input())
answer = 0
for _ in range(0, n):
    m = int(input())
    if is_prime(m):
        answer = answer + 1
print(answer)

Solution (Python):
def is_prime(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return n != 1

def witness(a, n, t, u):
    x = pow(a, u, n)  
    y = x

    for _ in range(0, t):
        y = (x * x) % n

        
        if y == 1 and x != 1 and x != (n - 1):
            return True
        x = y
    return y != 1

def is_probably_prime(n, witnesses):
    t = 1
    u = n // 2
    while u & 1 == 0:
        t = t + 1
        u >>= 1
    assert(2**t * u == n - 1)

    for a in witnesses:
        if a < n and witness(a, n, t, u):
            return False
    return True

def is_definitely_prime(n):
    if ((not (n & 1)) and n != 2) or (n < 2) or ((n % 3 == 0) and (n != 3)):
        return False
    if n <= 3:
        return True
    return is_probably_prime(n, [2, 7, 61])

n = int(input())
answer = 0
for _ in range(0, n):
    m = int(input())
    if is_definitely_prime(m):
        answer = answer + 1
print(answer)

Solution (Python):
def is_prime(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return n != 1

def witness(a, n, t, u):
    x = pow(a, u, n)  
    y = x

    for _ in range(0, t):
        y = (x * x) % n

        
        if y == 1 and x != 1 and x != (n - 1):
            return True
        x = y
    return y != 1

def is_probably_prime(n, witnesses):
    t = 1
    u = n >> 1
    while u & 1 == 0:
        t = t + 1
        u >>= 1
    assert(2**t * u == n - 1)

    for a in witnesses:
        if a < n and witness(a, n, t, u):
            return False
    return True

def is_definitely_prime(n):
    if ((not (n & 1)) and n != 2) or (n < 2) or ((n % 3 == 0) and (n != 3)):
        return False
    if n <= 3:
        return True
    return is_probably_prime(n, [2, 7, 61])

n = int(input())
answer = 0
for _ in range(0, n):
    m = int(input())
    if is_definitely_prime(m):
        answer = answer + 1
print(answer)

Solution (Python):
def is_prime(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return n != 1

def witness(a, n, t, u):
    x = pow(a, u, n)  
    y = x

    for _ in range(0, t):
        y = (x * x) % n

        
        if y == 1 and x != 1 and x != (n - 1):
            return True
        x = y
    return y != 1

def is_probably_prime(n, witnesses):
    t = 1
    u = n >> 1
    while u & 1 == 0:
        t = t + 1
        u >>= 1
    assert(2**t * u == n - 1)

    for a in witnesses:
        if a < n and witness(a, n, t, u):
            return False
    return True

def is_definitely_prime(n):
    if ((not (n & 1)) and n != 2) or (n < 2) or ((n % 3 == 0) and (n != 3)):
        return False
    elif n <= 3:
        return True
    else:
        return is_probably_prime(n, [2, 7, 61])

n = int(input())
answer = 0
for _ in range(0, n):
    m = int(input())
    if is_definitely_prime(m):
        answer = answer + 1
print(answer)

Solution (Python):
def witness(a, n, t, u):
    x = pow(a, u, n)  
    
    for _ in range(0, t):
        y = (x * x) % n

        
        if y == 1 and x != 1 and x != (n - 1):
            return True
        x = y
    return y != 1

def is_probably_prime(n, witnesses):
    t = 1
    u = n >> 1
    while u & 1 == 0:
        t = t + 1
        u >>= 1
    assert(2**t * u == n - 1)

    for a in witnesses:
        if a < n and witness(a, n, t, u):
            return False
    return True

def is_definitely_prime(n):
    if ((not (n & 1)) and n != 2) or (n < 2) or ((n % 3 == 0) and (n != 3)):
        return False
    elif n <= 3:
        return True
    else:
        return is_probably_prime(n, [2, 7, 61])

n = int(input())
answer = 0
for _ in range(0, n):
    m = int(input())
    if is_definitely_prime(m):
        answer = answer + 1
print(answer)

Solution (Python):
def witness(a, n, t, u):
    x = pow(a, u, n)  
    y = x

    for _ in range(0, t):
        y = (x * x) % n

        
        if y == 1 and x != 1 and x != (n - 1):
            return True
        x = y
    return y != 1

def is_probably_prime(n, witnesses):
    t = 1
    u = n >> 1
    while u & 1 == 0:
        t = t + 1
        u >>= 1
    assert(2**t * u == n - 1)

    for a in witnesses:
        if a < n and witness(a, n, t, u):
            return False
    return True

def is_definitely_prime(n):
    if ((not (n & 1)) and n != 2) or (n < 2) or ((n % 3 == 0) and (n != 3)):
        return False
    elif n <= 3:
        return True
    else:
        return is_probably_prime(n, [2, 7, 61])

n = int(input())
answer = 0
for _ in range(0, n):
    m = int(input())
    if is_definitely_prime(m):
        answer = answer + 1
print(answer)

Solution (Python):
def witness(a, n, t, u):
    x = pow(a, u, n)  

    for _ in range(0, t):
        y = (x * x) % n

        
        if y == 1 and x != 1 and x != (n - 1):
            return True
        x = y
    return y != 1

def is_probably_prime(n, witnesses):
    t = 1
    u = n >> 1
    while u & 1 == 0:
        t = t + 1
        u >>= 1
    assert(2**t * u == n - 1)

    for a in witnesses:
        if a < n and witness(a, n, t, u):
            return False
    return True

def is_definitely_prime(n):
    if ((not (n & 1)) and n != 2) or (n < 2) or ((n % 3 == 0) and (n != 3)):
        return False
    elif n <= 3:
        return True
    else:
        return is_probably_prime(n, [2, 7, 61])


n = int(input())
answer = 0
for _ in range(0, n):
    m = int(input())
    if is_definitely_prime(m):
        answer = answer + 1
print(answer)

Solution (Python):
import math
 
def prime(num):
  if num==1 or num==2 or num==3:
    return True
  for i in range(2,int(math.sqrt(num))+1):
    if num%i==0:
      return False
  else:
    return True
 
n=int(input())
ans=0
for i in range(n):
  tmp=int(input())
  if prime(tmp):
    ans+=1
print(ans)

Solution (Python):
import math

loopnum = int(input())
cnt = 0
for i in range(loopnum):

	chknum = int(input())
	rootnum = int(math.sqrt(chknum))

	for j in range(2,rootnum+1):
		if chknum % j == 0:
			break
	else:
		cnt += 1

	
	
	
	
	
	

print(cnt)

Solution (Python):
def isPrime(n):
    for i in range(2, n):
        if i * i > n:
            return 1
        if n % i == 0:
            return 0
    return 1

ans = 0
n = int(input())
for i in range(n):
    x = int(input())
    ans = ans + isPrime(x)

print(ans)

Solution (Python):
import math


def main():
    n = int(input())
    ans = 0
    for i in range(n):
        x = int(input())
        if x == 2:
            ans += 1
        elif x % 2 == 0:
            pass
        else:
            flag = True
            j = 3
            while j <= math.sqrt(x):
                if x % j == 0:
                    flag = False
                    break
                j += 2
            if flag:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import math
N = int(input())
ans = 0

for i in range(N):
    num = int(input())
    if num == 2:
        ans +=1
        continue
    rt = math.ceil(math.sqrt(num))
    div = 2
    bool = True
    while (rt >= div):
        if num % div:
            div += 1
        else:
            bool = False
            break
    if bool:
        ans += 1
print(ans)

Solution (Python):



def check_pn(num):
    if (num <2):
        return False
    elif (num==2):
        return True

    if (num%2 == 0):
        return False
    i = 3
    while (i <= num/i):
        if num % i == 0:
            return False
        i += 2

    return True


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

n=0
for data in listdata:
    ch = check_pn(data)
    n += ch

print (n)

Solution (Python):
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

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

try_num=int(input())
num_prime=0
for i in range(try_num):
    test_num=int(input())
    if isprime(test_num):
        num_prime += 1

print("%d"%(num_prime))

Solution (Python):
def is_prime(n):
    for i in range(2,n):
        if i*i > n:
            return True
        if n%i == 0:
            return False
    return True
c = 0
n = int(input())
for _ in range(n):
    data = int(input())
    if is_prime(data): c+= 1
print(c)

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

N =int(input())
count = 0
for i in range(0,N):
    num = int(input())
    count += int(prime_number(num))
print(count)

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


N = int(input())
num_list = [int(input()) for _ in range(N)]
print(sum(is_prime(num) for num in num_list))

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

def main():
    c = 0
    n = input()
    for i in range(n):
        if (isPrime(input())):
            c += 1
    print(c)

main()

Solution (Python):
import math
N = input()
c = 0
p = [0 for i in range(N)]
for i in range(0,N):
	p[i] = input()
for i in range(N):
	s = math.sqrt(p[i])
	j = 2
	while(j <= s):
		if(p[i]%j == 0):
			break
		j += 1
	if(j > s):
		c += 1
print c

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

Solution (Python):
import math

n = int(raw_input())

def isPrime(a):
    if a==2 or a==3:
        return 1
    if a<2 or a%2==0:
        return 0
        
    i = int(math.sqrt(a))+1
    for x in xrange(3,i):
        if a%x==0:
            return 0
    return 1

cnt = 0
for _ in xrange(n):
    a = int(raw_input())
    cnt += isPrime(a)
print cnt

Solution (Python):
import math

def isprime(x):
	sq = int(math.sqrt(x))
	for i in range(2, sq + 1):
		if x % i == 0:
			return False
	return x != 1

array = []
N = int(raw_input())
for i in range(0, N):
	array.append(int(raw_input()))

count = 0
for i in array:
	if isprime(i):
		count += 1
print count

Solution (Python):
primes = [2]

def is_prime(num):
    root = num ** 0.5
    for prime in primes:
        if root < prime:
            break
        if num % prime == 0:
            return False
    return True

def create_primes(primes, max):
    for i in range(primes[-1] + 1,max):
        if is_prime(i):
            primes += [i]

create_primes(primes, 10000)

n = int(input())
count = 0
for _ in range(n):
    num = int(input())
    count += 1 if is_prime(num) else 0
print(count)

Solution (Python):
primes = [2]

def is_prime(num):
    root = num ** 0.5
    for prime in primes:
        if root < prime:
            break
        if num % prime == 0:
            return False
    return True

def create_primes(primes, max):
    for i in range(primes[-1] + 1,max):
        if is_prime(i):
            primes += [i]

create_primes(primes, 10000)
count = 0
n = int(input())   
for _ in range(n):
    if is_prime(int(input())):
        count += 1
print(count)

Solution (Python):
primes = [2]

def is_prime(num):
    root = num ** 0.5
    for prime in primes:
        if root < prime:
            break
        if num % prime == 0:
            return 0
    return 1

def create_primes(primes, max):
    for i in range(primes[-1] + 1,max):
        if is_prime(i):
            primes += [i]

create_primes(primes, 10000)
count = 0
n = int(input())
s = [int(input()) for _ in range(n)]

print(sum(is_prime(i) for i in s))

Solution (Python):
primes = [2]

def is_prime(num):
    root = num ** 0.5
    for prime in primes:
        if root < prime:
            break
        if num % prime == 0:
            return 0
    return 1

def create_primes(primes, max):
    for i in range(primes[-1] + 1,max):
        if is_prime(i):
            primes += [i]

count = 0
n = int(input())
s = [int(input()) for _ in range(n)]

create_primes(primes, int(max(s) ** 0.5))

print(sum(is_prime(i) for i in s))

Solution (Python):
import sys


def sieve(N):
    is_prime = [True] * (N + 1)
    prime_list = []
    
    is_prime[0] = is_prime[1] = False
    
    prime_list.append(2)
    for i in range(3, N + 1, 2):
        if is_prime[i]:
            prime_list.append(i)
        for j in range(i * i, N, i):
            is_prime[j] = False
    
    return prime_list
    
primes = sieve(10001)
primes_set = set(primes)

def is_prime(num):
    if num in primes_set:
        return True
    elif num <= 10000:
        return False
    else:
        for prime in primes:
            if num % prime == 0:
                return False
        return True
    
if __name__ == '__main__':
    N = sys.stdin.readline()
    N = int(N)
    ans = 0
    for i in range(N):
        num = sys.stdin.readline()
        num = int(num)
        if is_prime(num): ans += 1
    
    sys.stdout.write(str(ans) + '\n')

Solution (Python):
import math
def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return False
    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))
                      
while True:
    try:
        n = int(raw_input())
        total = 0
        for k in range(n):
            if is_prime(int(raw_input())):
                total +=1
        print total
    except EOFError:
        break

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

count = 0

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

print(count)

Solution (Python):

import math

n = int(input())
prime_count = 0
for i in range(n):
    x = int(input())
    div = 1
    div_count = 0

    while div <= math.sqrt(x) and div_count < 3:
        if x % div == 0 and div == math.sqrt(x):
             div_count += 1
        elif x % div == 0 and div != math.sqrt(x):
             div_count += 2
        div += 1

    if div_count == 2:
        prime_count += 1

print(prime_count)

Solution (Python):

import math

n = int(input())
prime_count = 0
for i in range(n):
    x = int(input())
    div = 1
    div_count = 0

    while div <= math.sqrt(x) and div_count < 3:
        if x % div == 0 and div == math.sqrt(x):
             div_count += 1
        elif x % div == 0 and div != math.sqrt(x):
             div_count += 2
        div += 1

    if div_count == 2:
        prime_count += 1

print(prime_count)

Solution (Python):

import math

n = int(input())
prime_count = 0
for i in range(n):
    x = int(input())
    div = 1
    div_count = 0

    while div <= math.sqrt(x) and div_count < 3:
        if x % div == 0 and div == math.sqrt(x):
             div_count += 1
        elif x % div == 0 and div != math.sqrt(x):
             div_count += 2
        div += 1

    if div_count == 2:
        prime_count += 1

print(prime_count)

Solution (Python):

import math

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

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

print(c)

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


n = int( raw_input( ) )

cnt = i = 0
while i < n:
	num = int( raw_input( ) )
	if isPrime( num  ):
		cnt += 1
	i += 1

print( cnt )

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


n = int( input( ) )

cnt = i = 0
while i < n:
	num = int( input( ) )
	if isPrime( num  ):
		cnt += 1
	i += 1

print( cnt )

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


n = int( raw_input( ) )
nums = []
i = 0
while i < n:
	nums.append( int( raw_input( ) ) )
	i += 1
cnt = i = 0
for num in nums:
	if isPrime( num  ):
		cnt += 1
	i += 1

print( cnt )

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


n = int( raw_input( ) )
nums = []
i = 0
while i < n:
	nums.append( int( raw_input( ) ) )
	i += 1
cnt = i = 0
for num in nums:
	if isPrime( num  ):
		cnt += 1
	i += 1

print( cnt )

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


n = int( raw_input( ) )
nums = []
while 0 < n:
	nums.append( int( raw_input( ) ) )
	n -= 1
cnt = 0
for num in nums:
	if isPrime( num  ):
		cnt += 1

print( cnt )

Solution (Python):

from itertools import takewhile
from math import sqrt


def is_prime(primes, i):
    if i in primes:
        return True
    for p in takewhile(lambda x: x * x <= i, sorted(primes)):
        if i % p == 0:
            return False
    return True


def sieve_of_eratosthenes(max):
    is_prime = [True] * (max + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(sqrt(max)) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * i, max + 1, i):
            is_prime[j] = False
    return filter(lambda x: is_prime[x], range(max + 1))

primes = set(sieve_of_eratosthenes(10000))

n = int(input())
c = 0
for _ in range(n):
    i = int(input())
    if is_prime(primes, i):
        c += 1
print(c)

Solution (Python):

from itertools import count, takewhile


def prime():
    prime = []

    def _isPrime(n):
        for d in takewhile(lambda x: x * x <= n, prime):
            if n % d == 0:
                return False
        return True
    for i in count(2):
        if _isPrime(i):
            prime.append(i)
            yield(i)


def is_prime(primes, i):
    for p in takewhile(lambda x: x * x <= i, sorted(primes)):
        if i % p == 0:
            return False
    return True

primes = list(takewhile(lambda x: x < 10000, prime()))

n = int(input())
c = 0
for _ in range(n):
    i = int(input())
    if is_prime(primes, i):
        c += 1
print(c)

Solution (Python):
def miller_rabin(n):
    """ primality Test
        if n < 3,825,123,056,546,413,051, it is enough to test 
        a = 2, 3, 5, 7, 11, 13, 17, 19, and 23.
        Complexity: O(log^3 n)
    """
    if n == 2: return True
    if n <= 1 or not n&1: return False

    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]

    d = n - 1
    s = 0
    while not d&1:
        d >>= 1
        s += 1

    for prime in primes:
        if prime >= n: break
        x = pow(prime, d, n)
        if x == 1: break
        for r in range(s):
            if x == n - 1: break
            if r + 1 == s: return False
            x = x * x % n
    return True

N = int(input())
print(sum(1 for _ in range(N) if miller_rabin(int(input()))))

Solution (Python):
def miller_rabin(n):
    """ primality Test
        if n < 3,825,123,056,546,413,051, it is enough to test 
        a = 2, 3, 5, 7, 11, 13, 17, 19, and 23.
        Complexity: O(log^3 n)
    """
    if n == 2: return True
    if n <= 1 or not n&1: return False

    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]

    d = n - 1
    s = 0
    while not d&1:
        d >>= 1
        s += 1

    for prime in primes:
        if prime >= n: break
        x = pow(prime, d, n)
        if x == 1: break
        for r in range(s):
            if x == n - 1: break
            if r + 1 == s: return False
            x = x * x % n
    return True

N = int(input())
print(sum(1 for _ in range(N) if miller_rabin(input())))

Solution (Python):

from math import sqrt

def isPrime(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

def main():
	n = input()
	print sum([1 if isPrime(x) else 0 for x in [input() for _ in xrange(n)]])

if __name__ == '__main__':
	main()

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

result = 0
n = int(input())
for n in range(n):
    result += isprime(int(input()))
print(result)

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

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

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

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

Solution (Python):
from math import sqrt


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

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

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

n = int(input())
nums = [int(input()) for _ in range(n)]
print(sum(map(is_prime, nums)))