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 ≤ 108

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



Sample input:
5
2
3
4
5
6


Sample output:
3

Submission status: Accepted

Solution code:
def witness(a, n, t, u):
    x = pow(a, u, n)  # x0 = a^u mod nを計算
    y = x

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

        # 法nの下での1の非自明な平方根が存在するのは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)

Submission status: Accepted

Solution code:
def witness(a, n, t, u):
    x = pow(a, u, n)  # x0 = a^u mod nを計算

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

        # 法nの下での1の非自明な平方根が存在するのは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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

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

print(cnt)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#coding:utf-8
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)

Submission status: Accepted

Solution code:
#coding:utf-8
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)

Submission status: Accepted

Solution code:
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 )

Submission status: Accepted

Solution code:
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 )

Submission status: Accepted

Solution code:
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 )

Submission status: Accepted

Solution code:
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 )

Submission status: Accepted

Solution code:
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 )

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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)

Submission status: Accepted

Solution code:
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()))))

Submission status: Accepted

Solution code:
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())))

Submission status: Accepted

Solution code:
# coding: utf-8
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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 )

Submission status: Accepted

Solution code:
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 )

Submission status: Accepted

Solution code:
import pdb

n = int(raw_input())
count = 0
for x in xrange(n):
  target = int(raw_input())
  # pdb.set_trace()
  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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

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

#primes = set()
#def is_prime(n):
#  if n in primes:
#    return True
#
#  for m in range(2, n):
#    if is_prime(m) and n % m == 0:
#      return False
#
#  primes.add(n)
#  return True

# Proof:
# if n < d ^ 2 and n mod d = 0;
# n = ad (a in N)
# ad < d ^ 2
# a < d
# QED

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)]))

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()