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:
import math

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n = int(input())
c = 0
for i in range(n):
    m = int(input())
    if m != 2 and m % 2 == 0:
        c += 1
        continue
    i = 3
    while i * i <= m:
        if m % i == 0:
            c += 1
            break
        i += 2
print(n-c)

Submission status: Accepted

Solution code:
#78 素数

from math import sqrt

n = int(input())

ans = 0

for i in range(n):
    x = int(input())
    a = 1
    for z in range(2, int(sqrt(x))+1):
        if x % z == 0:
            a = 0
            break
    ans += a
print(ans)

Submission status: Accepted

Solution code:
import sys
prime = lambda x: True if x==2 else False if x<2 or not x%2 else pow(2,x-1,x)==1
inp = sys.stdin.readlines()
print(len([prime(e) for e in list(map(int, inp[1:])) if prime(e)==1]))

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

import math

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

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

def main():
    number=int(input())
    numbers=[]
    numbers=[int(input()) for _ in range(number)]
    counter=0
    for n in numbers:
        ans=is_prime(n)
        if ans ==True:
            counter+=1
        else:
            continue
    print(counter)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
cnt = 0

for i in range(n):
    x = int(input())
    rt_x = int(pow(x,1/2)) +1
    flag = 1
    for j in range(2,rt_x):
        if x%j==0:
            flag = 0
            break
    cnt += flag
print(cnt)

Submission status: Accepted

Solution code:
from math import sqrt
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, int(sqrt(n))+1):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True
m=int(input())
s=0
for i in range(m):
    l=int(input())
    if isPrime(l)==True:
        s+=1
print(s)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# 素数判定
# ふるいおとし

import sys
import math

loop = int(sys.stdin.readline())

# loop = 6

# arr = """2
# 3
# 4
# 5
# 6
# 7""".split('\n')

def is_prime(x):
    # エラトステネスのふるい
    if (x%2==0 and x!=2) or (x%3==0 and x!=3) or (x%5==0 and x!=5):
        return False
    for d in range(2, math.floor(math.sqrt(x))+1):
        if x%d==0:
            return False
    return True

count = 0
for _ in range(loop):
    x = sys.stdin.readline()
    # if is_prime(int(arr[_])):
    if is_prime(int(x)):
        count  += 1
print(count)

Submission status: Accepted

Solution code:
import math 

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

def countPrime(x):
    count = 0
    for e in x:
        if isPrime(e) is True:
            count += 1
    return count
    
n = int(input())
x = []
for i in range(n):
    x.append(int(input()))
print(countPrime(x))

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def sosu(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
    
    
n = int(input())
ans = 0
for i in range(n):
    m = int(input())
    if sosu(m):
        ans += 1
    else :
        ans += 0
print(ans)

Submission status: Accepted

Solution code:
import math

def prime(x):
    if x==2:
        return 'true'
    elif x%2==0:
        return 'false'
    else:
        i=3
        while i<=math.sqrt(x):
            if x%i==0:
                return 'false'
            i+=2
        return 'true'

n=int(input())
s=0
for j in range(n):
    x=int(input())
    r=prime(x)
    if r=='true':
        s+=1
print(s)

Submission status: Accepted

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 = i + 2
    return True
n=int(input())
count=0
for i in range(n):
    x=int(input())
    if isprime(x)==True:
        count+=1
print(count)

Submission status: Accepted

Solution code:
import math
def p(x):
	for i in range(2,int(math.sqrt(x))+1):
		if x%i == 0:
			return 0
	return 1
n=int(input())
ans=0
for i in range(n):
	x=int(input())
	if p(x):
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math
c = 0
n = int(input())

for j in range(n):
    x = int(input())
    
    if x == 2:
        c = c + 1
        
    if x < 2 or x % 2 == 0:
        c = c
        
    else:
        if x > 2 and x % 2 != 0:    
            i = 3
            a = 0
            while i <= math.sqrt(x):
                if x % i == 0:
                    c = c
                    a = a + 1
                    break
                else:
                    i = i + 2
            if a == 0:
                c = c + 1
print(c)

Submission status: Accepted

Solution code:
import math
def isprime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            return False
    return True
n=int(input())
sosuu=[]
for j in range(n):
    m=int(input())
    if isprime(m):
        sosuu.append(m)
print(len(sosuu))

Submission status: Accepted

Solution code:
N = int(input())

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

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

Submission status: Accepted

Solution code:
import math
n=int(input())
s=0
for i in range(n):
    x=int(input())
    a=0
    if x==2:
        s+=1
    else:
        for j in range(2,int(math.sqrt(x))+1):
            if x%j==0:
                a+=1
                break
        if a==0:
            s+=1
print(s)

Submission status: Accepted

Solution code:
def prime(n):
  p = 2
  while p * p <= n:
    if n % p == 0:
      return 0
    p += 1
  return 1

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

Submission status: Accepted

Solution code:
def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, int(n**0.5)+1):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True
total=0
if __name__ == "__main__":
    a=int(input())
    for i in range(a):
        b=int(input())
        if isPrime(b):
            total+=1
        else:
            pass
    print(total)

Submission status: Accepted

Solution code:
import math as ma
n=int(input())
m=0
for i in range (n):
    a = int(input())
    if a==2:
        m+=1
    if a>2:
        for j in range(2,int(ma.sqrt(a))+2):
            if a%j==0:
                break
            if j ==int(ma.sqrt(a))+1:
                m+=1
print(m)

Submission status: Accepted

Solution code:
import math
x = 0
a = int(input())
for _ in range(a):
    n = int(input())
    if n == 1:
        x = x + 1
        continue
    for i in range(2,int(math.sqrt(n))+1):
        if n % i == 0:
            x = x + 1
            break
print(a-x)

Submission status: Accepted

Solution code:
import math
def sosu(x):
    if x == 2:
        return 1
    elif x < 2 or x % 2 == 0:
        return 0
    i = 3
    while i <= math.sqrt(x):
        if x % i == 0:
            return 0
        i += 2
    return 1
    
n = int(input())
m = 0
for i in range(n):
    a = int(input())
    b = sosu(a)
    m += b 
print(m)

Submission status: Accepted

Solution code:
import math
n=int(input())
s=0
for i in range(n):
    a=int(input())
    b=math.ceil(a**0.5)
    if a==2:
        s+=1
    elif a%2==0 or a < 2:
        continue
    else:
        c=0
        for j in range(3,b+1,2):
            if a%j==0:
                c+=1
                break
        if c==0:
            s+=1
print(s)

Submission status: Accepted

Solution code:
import math
n = int(input())
lst = [int(input()) for i in range(n)]
s = 0

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

for i in range(n):
    if isprime(lst[i]):
        s += 1

print(s)

Submission status: Accepted

Solution code:
prime=[2]
lst=[1]*(10**4+1) 

for i in range(3,10**4,2):
    if lst[i]:
        prime.append(i)
        token=3
        while i*token<10**4:
            if lst[i*token]: lst[i*token]=0
            token+=2

n=int(input())
sm=0
for _ in range(n):
    np=int(input())
    if np<=10**4:
        sm+=np in prime
    else :
        for p in prime:
            if np%p==0 : break
        else : sm+=1

print(sm)

Submission status: Accepted

Solution code:
def is_prime(q, k=50):
    q = abs(q)
    if q == 0:
        return False
    elif q == 2:
        return True
    return pow(2, q-1, q) == 1


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

print(result)

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
import math

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

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

    return True

try:
    N = int(input().strip())
    nums = [int(input()) for i in range(N)]
except ValueError:
    print('ValueError')

num_p = 0
for i in nums:
    if is_prime(i)==True:
        num_p += 1
print(str(num_p))

Submission status: Accepted

Solution code:
# coding: utf-8
#78
import math

n = int(input())
B=0

for i in range(n):
    N = int(input())
    A=0
    s = int(math.sqrt(N)+1)
    if N==2:
        B += 1
    else:
        for j in range(2,s):
            if N%j==0:
                A += 1
                break
        if (A==0):
            B += 1
print(B)

Submission status: Accepted

Solution code:
def isPrime(x):
    if x == 2:
        return True
    if x < 2 or x & 1 == 0:
        return False
    for i in range(3, int(x ** 0.5 + 1)):
        if x % i == 0:
            return False
    return True

print(sum(map(isPrime, [int(input()) for _ in range(int(input()))])))

Submission status: Accepted

Solution code:
import math


def main():
    # 入力
    n = int(input())
    elements = [int(input()) for i in range(n)]
    count = 0

    for element in elements:
        if prime_num(element) == True:
            count += 1

    print(count)


def prime_num(element):
    if element == 2:
        return True
    elif element < 1 or element % 2 == 0:
        return False
    else:
        p = 3
        while p <= math.sqrt(element):
            if element % p == 0:
                return False
            p += 2
        return True


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def sosu(n):
    if n<2:
        return False
    if n==2:
        return True

    if n%2==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())
j=0

for i in range(n):
    k=int(input())
    if sosu(k):
        j+=1

print(j)

Submission status: Accepted

Solution code:
import math

n = int(input())
cnt = 0
for i in range(n):
    num = int(input())
    flag = 1
    if num == 2:
        flag = 1
    elif num % 2 == 0 or num < 2:
        flag = 0
    else:
        for j in range(3, int(math.sqrt(num))+1, 2):
            if num % j == 0:
                flag = 0
                break
    if flag:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
def judge(n):
    if n == 2:
        return True
    elif n < 2 or n%2 == 0:
        return False
    else:
        i = 3
        while i<=n**0.5:
            if n%i==0:
                return False
            i = i + 2
    return True        

n = int(input())
num = [int(input().strip()) for _ in range(n)]

sum = 0
for i in range(n):
    if judge(num[i]):
        sum = sum + 1
print(sum)

Submission status: Accepted

Solution code:
import math

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

    if n % 2 == 0 and n > 2:
        return False
    
    for i in range(2, math.floor(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

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

Submission status: Accepted

Solution code:
import math

result = []

n = int(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

for _ in range(n):
    x = int(input())
    if isprime(x):
        result.append(x)
    
print(len(result))

Submission status: Accepted

Solution code:
def is_prime(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
        else:
            i += 2
    
    return True

N = int(input())    
counter = 0
for _ in range(N):
    if is_prime(int(input())):
        counter += 1
    else:
        continue

print(counter)

Submission status: Accepted

Solution code:
N = int(input())

cnt = 0
for _ in range(N):
    n = int(input())
    if n!=2 and n%2 == 0:
        cnt += 1
        continue
    i = 3
    while i**2 <= n:
        if n%i == 0:
            cnt += 1
            break
        i += 2

print(N-cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,*aa = map(int, open(0).read().split())

def is_prime(x):
    if x in [0,1]:
        return False
    if x == 2:
        return True
    if not x%2:
        return False
    for i in range(3,int(x**0.5+1e-8)+1,2):
        if not x%i:
            return False
    return True

print(sum(is_prime(a) for a in aa))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

    return True


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#ALDS1_1_C
b = 0
n = int(input())
for i in range(n):
    a = int(input())
    c = 0
    if a == 2:
        b += 1
    else:
        for j in range(2,int(a**(1/2))+1):
            if a%j == 0:
                c += 1
                break
        if c == 0:
            b += 1
print(b)

Submission status: Accepted

Solution code:
import math
def sosu(x):
    if x == 1:
        return False

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

x = []
n = int(input())
for i in range(n):
    k = int(input())
    if sosu(k):
        x.append(k)
print(len(x))

Submission status: Accepted

Solution code:
import math
def isprime(x):
    if x==2:
        return 1
    elif x<2 or x%2==0:
        return 0
    else:
        i=3
        while i<=math.sqrt(x):
            if x%i==0:
                return 0
            i=i+2
        return 1

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

Submission status: Accepted

Solution code:
import math
n=int(input())

a=[int(input()) for i in range(n)]
k=0
l=int(math.sqrt(max(a)))
for i in range(n):
    if a[i]!=1 and a[i]>0:
        for j in range(2,l):
            if a[i]%j==0 and a[i]!=j:
                m=2
                break
            m=1
        if a[i]==2:
            m=1
        if m==1:
            k+=1
print(k)

Submission status: Accepted

Solution code:
import math

def is_prime(num):
    if num < 2:
        return False
    if num == 2 or num == 3 or num == 5:
        return True
    if num % 2 == 0 or num % 3 == 0 or num % 5 == 0:
        return False

    # 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    num_sqrt = math.sqrt(num)
    while prime <= num_sqrt:
        if num % prime == 0:
            return False
        prime += step
        step = 6 - step

    return True


n = int(input())
arr = []
count = 0

for i in range(n):
    arr.append(int(input()))

for j in arr:
    if is_prime(j):
        count += 1
print(count)

Submission status: Accepted

Solution code:
import math

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

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

    index = 3
    while index <= int(math.sqrt(num)) + 1:
        if num % index == 0:
            return False
        index += 2
    return True


n = int(input())

output = 0
for index in range(n):
    num = int(input())
    if is_prime(num):
        output += 1
print(output)

Submission status: Accepted

Solution code:
def isPrime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            break
        i += 1
    else:
        return True
    return False


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

Submission status: Accepted

Solution code:
n=int(input())
cnt=0
for i in range(n):
  p=int(input())
  for j in range(2,int(p**.5)+1):
    if p%j==0:break
  else:cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
P = [int(input()) for i in range(n)]

def isPrime(n):
    s_n = int(n**0.5)
    if n < 2:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    else:
        for i in range(3, s_n+1, 2):
            if n % i == 0:
                return False
    return True
            
cnt = 0
for i in P:
    cnt += isPrime(i)

print(cnt)

Submission status: Accepted

Solution code:
import math
m = int(input())
prime = []
for j in range(m):
    n = int(input())
    pri  = []
    
    i = 2
    while i <= math.sqrt(n):
        while n % i == 0:
            pri.append(i)
            n//=i
        i+=1
    
    if n != 1:
        pri.append(n)
        
    if len(pri) == 1:
        prime.append(pri[0])
    
print(len(prime))

Submission status: Accepted

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


n = int(input())

ans = 0
for i in range(n):
    x = int(input())
    ans += 1 if judge(x) else 0

print(ans)

Submission status: Accepted

Solution code:
import math
count = 0
while True:
    try:
        n = int(input())
        if n == 2 or n == 3 or n == 5 or n == 7:
            count += 1
        if n > 3 and n % 2 != 0:
            for i in range(3,int(math.sqrt(n))+1):
                if n % i == 0:
                    break
                elif i == int(math.sqrt(n)):
                    count += 1
    except  EOFError:
        break
print(count)

Submission status: Accepted

Solution code:
def isprime(N):
    for i in range(2, int(N**0.5)+1):
        if N % i == 0:
            return False
    return True
    
def prime_number(N):
    pn = []
    flg = [0] * (N+1)
    for i in range(2, N+1):
        if flg[i] > 0:
            continue
        for j in range(i, N+1, i):
            flg[j] = 1
        pn.append(i)
    return pn

N = int(input())
cnt = 0
for _ in range(N):
    num = int(input())
    cnt += isprime(num)
print(cnt)

Submission status: Accepted

Solution code:
import math


N=int(input())

S=[]
T=[]
for i in range(N):
    S.append(int(input()))

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

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

    return True




for i in range(N):
    
    tmp=is_prime(S[i])
    if tmp==True:
        T.append(S[i])
print(len(T))

Submission status: Accepted

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


n = int(input())
ans = 0

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
a=int(input())
b=[int(input()) for i in range(a)]

def isPrime(x):
    if x==2:
        return True
    if x<2 or x%2==0:
        return False
    i=3
    while i<=x**0.5:
        if x%i==0:
            return False
        i+=2
    return True
ans=0
for i in b:
    if isPrime(i):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    f = 3
    root_n = int(n ** 0.5) + 1
    while f <= root_n:
        if n % f == 0:
            return False
        f += 2

    return True


def main():
    n = int(input())
    ans = 0
    for _ in range(n):
        x = int(input())
        ans += is_prime_number(x)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#ALDS1_1_C:   Prime Numbers
import math
def prime(n):
    limit = math.sqrt(n)
    if n == 2: return 1
    if n < 2 or n % 2 == 0: return 0
    
    i = 3
    while i <= limit:
        if n % i == 0: return 0
        else:
            i += 2
    return 1
        
n = int(input())
res = 0
for _ in range(n):
    res += prime(int(input()))
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

prime_dict = defaultdict(lambda : True)
prime_dict[0],prime_dict[1] = False,False
finished = defaultdict(lambda : False)

ans = 0
for a in A:
    if not finished[a]:
        root_a = int(a**0.5)
        for i in range(2,root_a + 1):
            if a % i == 0:
                prime_dict[a] = False
                break
        finished[a] = True
    if prime_dict[a]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def get_primes(maxn):
    c = int(maxn**0.5)+1
    sieve = [True]*c
    sieve[0] = sieve[1] = False
    primes = []
    for p in range(2, c):
        if sieve[p]:
            primes.append(p)
            for i in range(2*p, c, p):
                sieve[i] = False
    return primes


def is_prime(n, primes):
    if n <= 1:
        return False
    c = int(n**0.5)+1
    for p in primes:
        if p > c:
            break
        if n != p and n % p == 0:
            return False
    return True


def solve():
    n, *A, = map(int, open(0).read().split())

    primes = get_primes(max(A))
    ans = 0
    for a in A:
        if is_prime(a, primes):
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
def p(x):
    if x==2:
        return True
    
    if x==1 or x%2==0:
        return False
    
    i=3
    while i <=math.sqrt(x):
        if x%i==0:
            return False
        i=i+2
    return True
    
c=0
n=int(input())
for i in range(n):
    x=int(input())
    if p(x)==True:
        c+=1
print(c)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import math

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

n = int(stdin.readline().rstrip())
cnt = 0

for i in range(n):
  v = int(stdin.readline().rstrip())
  if is_prime_number(v):
    cnt += 1
else:
  print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
cnt=0
for i in range(n):
  x=int(input())
  s=0
  for j in range(2,(int(pow(x,0.5)//1)+1)): 
    if x%j==0:
      s=1
      break
  if s==0:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from math import sqrt
n = int(input())
ans = 0
for i in range(n):
    x = int(input())
    ok = 1
    for z in range(2, int(sqrt(x))+1):
        if x % z == 0:
            ok = 0
            break;
    ans += ok
print(ans)

Submission status: Accepted

Solution code:
import random


def judge_miller(n, rep):
    if(n == 1):
        return False
    if(n == 2):
        return True
    if(n % 2 == 0):
        return False
    d = n - 1
    while(d & 1 == 0):
        d >>= 1
    for k in range(rep):
        cp_d = d
        a = random.randint(2, n - 1)
        may_prime = False
        x = pow(a, d, n)
        if(x == 1):
            may_prime = True
        while((not may_prime) and x != n - 1 and d != n - 1):
            if(x == n - 1):
                may_prime = True
            d <<= 1
            x = (x * x) % n
        if(x == n - 1):
            may_prime = True
        if(not may_prime):
            return False
        d = cp_d
    return True


n = int(input())
cnt = 0
for i in range(n):
    x = int(input())
    res = judge_miller(x, 15)
    if(res):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# 素数の数を数える
# n
# i1
# i2
# ...
# in
import math

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

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

    return True

n = int(input())
print(sum([(1 if is_prime(int(input())) else 0) for _ in range(n)]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

"""Determines whether an input integer is prime, by trial division.

Verification: [ALDS1_1_C](https://onlinejudge.u-aizu.ac.jp/status/users/hamukichi/submissions/1/ALDS1_1_C/judge/4573080/Python3)
"""


def is_prime_trial_division(n):
    """Determing whether the given integer `n` is prime by trial division.

    """

    assert n > 0
    if n < 2:
        return False
    else:
        for i in range(2, n):
            if i * i > n:
                break
            elif n % i == 0:
                return False
        return True


def count_primes(ms):
    return sum(is_prime_trial_division(m) for m in ms)


def main():
    n = int(input())
    ms = [int(input()) for _ in range(n)]
    print(count_primes(ms))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

c = 0

for _ in range(N):
    if isprime(int(input())):
        c += 1

print(c)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    flag = True
    cnt = 0
    for _ in range(n):
        i = int(input())
        if i == 2:
            flag = True
        else:
            for j in range(2, int(-(-i**0.5//1))+1):
                if i%j == 0:
                    flag = False
                    break
        if flag:
            cnt += 1
        flag = True   
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

n = int(input())
a = 0

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

Submission status: Accepted

Solution code:
def P(n):
    for i in range(2,n):
        if i*i>n:
            return True
        if n%i==0:
            return False
    return True

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

Submission status: Accepted

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

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

Submission status: Accepted

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


def resolve():
    N = int(input())
    ans = 0
    for _ in range(N):
        ans += 1 if is_prime(int(input())) else 0
    print(ans)


resolve()