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: Memory Limit Exceeded

Solution code:
import sys

lines = sys.stdin.readlines()

n = lines[0]
lst = map(lambda x:int(x), lines[1:])

c = 0
for v in lst:
    for j in range(2,v+1):
        if v%float(j) == 0:
            m = j
            break
    if m == v:
        c += 1



print c

Submission status: Memory Limit Exceeded

Solution code:
N = input()
pnum_count = N
for _ in range(N):
    n = input()
    for i in range(2, n):
        if n % i == 0:
            pnum_count -= 1
            break
print pnum_count

Submission status: Memory Limit Exceeded

Solution code:
N = input()
prime = 0

for _ in range(N):
    n = input()

    
    for i in range(2,n):
        if n%i == 0:
            break
    else:
        prime += 1

print prime

Submission status: Memory Limit Exceeded

Solution code:
from operator import itemgetter

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

if __name__ == "__main__":
    N = int(input())
    f = itemgetter(*[int(input()) for _ in range(N)])
    print(sum(f(eratosthenes(10**8))))

Submission status: Memory Limit Exceeded

Solution code:
def judge(int):
    if int == 2:return 1
    elif int <= 1 :return 0
    for i in range(2,int - 1):
        if int%i == 0: return 0
    return 1



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

Submission status: Memory Limit Exceeded

Solution code:
n = int(input())
A = [int(input()) for x in range(n)]
A_max = max(A)

p_table = [x for x in range(2,A_max+1)]
p_table
for p in p_table:
    j=2
    while 0 < j*p-2 < len(p_table):
            p_table[j*p-2] = 0
            j += 1
p_table = [x for x in p_table if x != 0]

count = 0
for a in A:
    if a in p_table:
        count += 1

print(count)

Submission status: Memory Limit Exceeded

Solution code:
import sys

def isPrime(x):
     if x == 1:
          return False
     if x == 2:
          return True
     for num in range(x - 2):
          if x%(num+2) == 0:
               return False
     return True

input = []
for line in sys.stdin:
     input.append(int(line))
##input = [2, 4, 7, 1, 2, 3, 1, 11]
count = 0
for num in set(input):
     if isPrime(num):
          count += 1

print count

Submission status: Memory Limit Exceeded

Solution code:
from math import sqrt
def isprime(farm, prime):
	first = min(farm)
	maxfarm = max(farm)
	while len(farm) > 0 and sqrt(maxfarm) > first:
		first = min(farm)
		prime.append(first)
		maxfarm = max(farm)
		dellst = range(first, maxfarm+1, first)
		farm = set(farm - set(dellst))
	return prime.extend(farm)
 
n = int(input())
inlst = []
for i in range(n):
    inlst.append(int(input()))
farm = set(range(3, max(inlst)+1, 2))
prime = [1,2]
 
if len(farm) > 0:
    isprime(farm, prime)
     
out = list(set(inlst) & set(prime))
print(len(out))

Submission status: Memory Limit Exceeded

Solution code:
def prime_number(num):
    if num == 2:
        return 1
    elif num%2 != 0:
        for j in range(3, num, 2):
            if num%j == 0:
                return 0
        return 1
    else:
        return 0

n = int(raw_input())
num = [0 for i in range(n)]
for i in range(n):
    num[i] = int(raw_input())

count = 0
for i in range(n):
    if prime_number(num[i]) == 1:
        count += 1

print count

Submission status: Memory Limit Exceeded

Solution code:
def prime_number(num):
    if num == 2:
        return 1
    elif num%2 != 0:
        for j in range(3, num, 2):
            if num%j == 0:
                return 0
        return 1
    else:
        return 0

n = int(raw_input())

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

print count

Submission status: Memory Limit Exceeded

Solution code:
def isPrimeNum(x):
	for i in range(2, x):
		if x % i == 0:
			return False
	return True

# input
n = int(raw_input())

if n < 1 or n > 10000:
	exit()

count = 0

for i in range(0, n):
	e = int(raw_input())
	if e < 2 or e > 1000000000:
		exit()
	if isPrimeNum(e):
		count += 1

print count

Submission status: Memory Limit Exceeded

Solution code:
from math import sqrt
n = int(input())
e = sorted([int(input()) for _ in range(n)])
L, pnum, tmp = sqrt(e[-1]+1), [], [i for i in range(2, e[-1]+1)]
while tmp[0] < L:
    v = tmp.pop(0)
    pnum.append(v)
    tmp = list(filter(lambda x: x%v!=0, tmp))
for t in tmp: pnum.append(t)
print(sum(1 for v in e if v in pnum))

Submission status: Memory Limit Exceeded

Solution code:
N=10**8
p=[i for i in range(N)]
for i in range(2,int(N**0.5)+1):
    if p[i]:
        for j in range(i*i,N,i):p[j]=0
p=sorted(set(p))[2:]
n=int(input())
print(sum(1 for _ in range(n) if int(input()) in p))

Submission status: Memory Limit Exceeded

Solution code:
n = int(input())
a = {int(input()) for i in range(n)}


def prime_list(a):
    p = [i for i in range(2, max(a) + 1)]
    N = len(p)
    m = int(N**0.5) + 1
    for i in range(m):
        if p[i]>0:
            for j in range(i + 1, N):
                if p[j] % p[i] == 0:
                    p[j] = 0
    p = set(p)
    return p

p = prime_list(a)
primes = p & a
print(len(primes))

Submission status: Memory Limit Exceeded

Solution code:
n=int(input())
answer=0
hani=10**2

max=0
number=[]
for i in range(n):
    t=int(input())
    if t>max:
        max=t
    number.append(t)


hani=max
k=2
numlist=[0 for i in range(hani+1)]
numlist[0]=-1
numlist[1]=-1


read=2
while read<=hani**(0.5):
    if numlist[read]==0:
        k=1
        while read*(k+1)<=hani:
            numlist[read*(k+1)]=-1
            k+=1
    read+=1

for i in range(n):
    if numlist[number[i]]==0:
        answer+=1



print(answer)

Submission status: Memory Limit Exceeded

Solution code:
x = 10**8
plist = [True for _ in range(x)]
prime_list =[]
plist[0], plist[1] = False, False
for i in range(4, x, 2):
    plist[i] = False
for i in range(1, 10, 2):
    if plist[i] == True:
        for j in range(i*2, len(plist) + 1, i):
            if j >= len(plist):
                break
            plist[j] = False
for i in range(len(plist)):
    if plist[i] == True:
        prime_list.append(i)

def prime_number():
    n = int(input())
    count = 0
    for _ in range(n):
        if int(input()) in prime_list:
            count += 1
    print(count)


if __name__ == "__main__":
    prime_number()

Submission status: Memory Limit Exceeded

Solution code:
num = set()
try:
	while True:
		num.add(eval(input()))
except EOFError:
	max_num = max(num)
	is_primer = [True for _ in range(max_num+1)]
	for i in range(2,int(len(is_primer)/2)):
		if is_primer[i]:
			for j in range(i*2,len(is_primer),i):
				is_primer[j] = False
	count = 0
	for x in num:
		count = count + (1 if is_primer[x] else 0)
	print(count)

Submission status: Memory Limit Exceeded

Solution code:
max_num = 100000000
is_primer = [True for _ in range(max_num+1)]
for i in range(2,int(len(is_primer)/2)):
	if is_primer[i]:
		for j in range(i*2,len(is_primer),i):
			is_primer[j] = False
num = set()
try:
	while True:
		num.add(eval(input()))
except EOFError:
	count = 0
	for x in num:
		count = count + (1 if is_primer[x] else 0)
	print(count)

Submission status: Memory Limit Exceeded

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

b=int(input())
z=[]
for i in range(b):
   z+=[int(input())]
z.sort()

n=z[len(z)-1]
a=[j for j in range(n+1)]
def eratos(n):
    for i in range(n+1):

        a[0]=a[1]=False
        if isPrime(i):
            j= i+i
            while j<=n:
                a[j]=False
                j=j+i
    return a
a=eratos(n)
count=0
for i in z:
    if i in a:
        count+=1
print(count)

Submission status: Memory Limit Exceeded

Solution code:
import math

def hurui(a):
    ret = [True for i in range(a+1)]
    for i in range(2, int(math.sqrt(a))+2):
        for j in range(i*2, a+1, i):
            ret[j] = False

    return ret

n = int(input())
l = hurui(100000000)
ans = 0
for i in range(n):
    a = int(input())
    if l[a]:
        ans += 1

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import math

def hurui(a):
    ret = [True for i in range(a+1)]
    for i in range(2, int(math.sqrt(a))+2):
        if not ret[i]:
            continue
        for j in range(i*2, a+1, i):
            ret[j] = False

    return ret

ans = 0
m = 0
n = int(input())
a = []
for i in range(n):
    x = int(input())
    if x > m:
        m = x
    a.append(x)
l = hurui(m)

for i in range(n):
    if l[a[i]]:
        ans += 1

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import math

ans = 0
m = 0
n = int(input())
a = []
for i in range(n):
    x = int(input())
    if x > m:
        m = x
    a.append(x)

l = [True for i in range(m+1)]
for i in range(2, int(math.sqrt(m))+2):
    if not l[i]:
        continue
    for j in range(i*2, m+1, i):
        l[j] = False

for i in range(n):
    if l[a[i]]:
        ans += 1

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
N =int(input())
prime = [1]*100000001
ans = 0

def eratos():
    prime[0] ,prime[1] = 0,0
    for i in range(2,10000):
        if prime[i] == 1:
            j = i + i
            while j <= 100000000:
                prime[j] = 0
                j += i

eratos()
for i in range(N):
    x = int(input())
    if prime[x] == 1:
        ans += 1
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
s=[]
a=[int(i) for i in range(2,100000000)]
while a!=[]:
    t=a[0]
    a=[i for i in a if i % t !=0]
    s.append(t)

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

Submission status: Memory Limit Exceeded

Solution code:
s=[2]
a=[int(i) for i in range(2,100000000)]
a=[i for i in a if pow(2 ,i-1, i) ==1]
print(a)
while a!=[]:
    t=a[0]
    a=[i for i in a if i % t !=0]
    s.append(t)

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

Submission status: Memory Limit Exceeded

Solution code:

s=[2]
a=[int(i) for i in range(2,100000000)]
a=[i for i in a if pow(2 ,i-1, i) ==1]









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

Submission status: Memory Limit Exceeded

Solution code:
# coding:utf-8
array = []
cnt = 0
n = input()
for i in range(n):
    array.append(input())
for value in array:
    for value2 in range(2,value):
        if value % value2 == 0:
            break
    else:
        cnt += 1
print cnt

Submission status: Memory Limit Exceeded

Solution code:
c = 0
def is_prime(n):
    b = list(range(2, int(n**1/2)+1))
    for i in b:
        if not(n % i):
            return False
    return True
for _ in range(int(input())):
    if is_prime(int(input())):
        c += 1
print(c)

Submission status: Memory Limit Exceeded

Solution code:
from math import sqrt, ceil


def ene(n):
    #配列の初期化
    alist = [True] * n               # 100個の配列を準備、すべての配列の中身に1を代入
    alist[0] = alist[1] = False             # 0と1は除外

    #素数検索
    for i in range(4, n, 2):  # 2の倍数(2以外の偶数)は除外
        alist[i] = False

    for i in range(3, ceil(sqrt(n)), 2): # 3から100の平方根までの奇数
        if alist[i]:
            for j in range(i * 2, n, i):   # 奇数の倍数を除外
                alist[j] = False

    return alist

def main():
    alist = []
    for _ in range(int(input())):
        alist.append(int(input()))

    amax = max(alist)
    ene_list = ene(amax+1)
    result = 0
    for i in alist:
        if ene_list[i]:
            result += 1
    print(result)

main()

Submission status: Memory Limit Exceeded

Solution code:
import math

def Eratos(n):
	primes = [2]
	num = [2*i+1 for i in range(1,n//2)]
	tmp = []

	top = 1
	while top < math.sqrt(n):
		top = num[0]
		for i in range(1,len(num)):
			if num[i] % top != 0:
				tmp.append(num[i])
		num = tmp
		tmp = []
		primes.append(top)
	for i in range(len(num)):
		primes.append(num[i])
	return primes

n = int(input())
cont = 0
nums = []
for i in range(n):
	a = int(input())
	nums.append(a)
nums.sort()
primes = Eratos(nums[n-1]+1)
for i in range(n):
	if primes.count(nums[i])!=0:
		cont += 1
print(cont)

Submission status: Memory Limit Exceeded

Solution code:
import math

def Eratos(n):
	primes = [2]
	num = [2*i+1 for i in range(1,n//2)]
	tmp = []

	top = 1
	while top < math.sqrt(n):
		top = num[0]
		for i in range(1,len(num)):
			if num[i] % top != 0:
				tmp.append(num[i])
		num = tmp
		tmp = []
		primes.append(top)
	for i in range(len(num)):
		primes.append(num[i])
	return primes

n = int(input())
cont = 0
primes = Eratos(99999997)
for i in range(n):
	a = int(input())
	if primes.count(a)!=0:
		cont += 1
print(cont)

Submission status: Memory Limit Exceeded

Solution code:
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):
		if i * i > n:
			break
		for j in range(i*i, n, i):
			is_prime[j] = False
	return is_prime

is_prime = eratos(100000000)
n = int(input())
ans = 0
for _ in range(n):
    x = int(input())
    if is_prime[x] is True:
        ans += 1

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import sys

flag = False
cnt = 0

num = input()

for i in range(num):
	data = input()
	for j in range(2,data):
		if data%j == 0:
			flag = True
			break
	if flag == False:
		cnt += 1
	flag = False
print cnt

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
cnt = n = int(stdin.readline())
for _ in range(n):
    v = int(stdin.readline())
    if v == 2:
        continue
    elif v % 2 == 0:
        cnt -= 1
    else:
        for i in range(3, v//2, 2):
            if v % i == 0:
                cnt -= 1
                break
print(cnt)

Submission status: Memory Limit Exceeded

Solution code:
import sys

def checkprime(a):
    for t in range (a-2):
        s=t+2
        if a%s==0:
            return 0
    return 1
    

count =0

for line in sys.stdin:
    a=int(line.strip())
    count =count + checkprime(a)

print count

Submission status: Memory Limit Exceeded

Solution code:
def main():
    N = int(raw_input())
    count = 0
    for i in range(0,N):
        a = int(raw_input())
        if checkPrimeNum(a):
            count += 1
    print count

cached = [2]
def checkPrimeNum(num):
    for i in range(2,num):
        # check i is prime num
        if cached.count(i) >1:
            isPrime = True
            for j in range(2,i):
                if i % j == 0:
                    isPrime = False
                    break
            if isPrime:
                print ""
                cached.append(i)
        if  num % i == 0:
            return False
    if cached.count(num) == 0:
        cached.append(num)
    return True

main()

Submission status: Memory Limit Exceeded

Solution code:
n = input()
count = 0
for i in range(n):
    x = input()
    for j in range(2,x):
        if x % j == 0: break
    else:
        count += 1
print count

Submission status: Memory Limit Exceeded

Solution code:
n = input()
count = 0
for i in range(n):
    x = input()
    if x == 2: count += 1
    elif x % 2 != 0:
        for j in range(3,int(x*0.5+1),2):
            if x % j == 0: break
        else: count += 1
print count

Submission status: Memory Limit Exceeded

Solution code:
import math

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

r = max(a)+1
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

count = 0
for i in a:
    count += p[i-1]
    
print count

Submission status: Memory Limit Exceeded

Solution code:
import math

r = 10000000
sqrt = int(math.sqrt(r))
p = [1 for i in range(r)]
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

count = 0
while True:
    try:
        n = int(raw_input())
        if p[n-1]:
            count += 1
    except:
        break
print count

Submission status: Memory Limit Exceeded

Solution code:
import math

r = 50000000
sqrt = int(math.sqrt(r))
p = [1 for i in range(r)]
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

count = 0
n = int(raw_input())
for i in range(n):
    m = int(raw_input())
    if p[m-1]:
        count += 1

print count

Submission status: Memory Limit Exceeded

Solution code:
import math
n = int(raw_input())
ls = [int(raw_input()) for i in range(n)]
r = max(ls)+1
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]
   
ans = 0
for i in ls:
    ans += p[i-1]
print ans

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    #print str
    num=int(str)
    st.add(num)
sum=0
for nm in st:
    if check(nm):
        sum+=1
print sum

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""素数を求める。

以下の性質を用いる。
合成数 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)

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
    
s=[]
for _ in range(int(input())):
    s.append(is_prime(int(input())))
print(sum(s))

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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