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

Solution code:
def primesUpTo(n):
    primes = [2]
    if n < 2:
        return []

    for i in range(3, n + 1, 2):
        isPrime = True
        for prime in primes[1:]:
            if prime > n ** (1 / 2):
                break
            if i % prime == 0:
                isPrime = False
                break
        if isPrime:
            primes.append(i)

    return primes

n = int(input())
l = [int(input()) for _ in range(n)]
primes = primesUpTo(max(l))

print(len([x for x in l if x in primes]))

Submission status: Time Limit Exceeded

Solution code:
prime = set([2])
for i in range(3, 100000000, 2):
    for j in prime:
        if i % j == 0:
            break
    else:
        prime.add(i)
n = int(input())
cnt = 0
for i in (int(input()) for _ in range(n)):
    if i in prime:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

count = 0

inarr = set()

for line in sys.stdin:
    inarr.add(int(line))

for n in inarr:
    if n == 2:
        count += 1
        continue

    jdg = True
    for i in range(2, n):
        if n % i == 0:
            jdg = False
            break
    if jdg:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

count = 0

inarr = set()

for line in sys.stdin:
    n = int(line)

    if n == 2:
        inarr.add(n)
        continue

    jdg = True
    for i in range(2, n):
        if n % i == 0:
            jdg = False
            break
    if jdg:
        inarr.add(n)

print(len(inarr))

Submission status: Time Limit Exceeded

Solution code:
import sys

count = 0

number = int(input())

for line in sys.stdin:
    n = int(line)
    if n == 2:
        count += 1
        continue

    if n % 2 == 0:
        continue

    jdg = True
    for i in range(3, n, 2):
        if n % i == 0:
            jdg = False
            break
    if jdg:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

count = 0

number = int(input())

for line in sys.stdin:
    n = int(line)
    if n == 2:
        count += 1
        continue

    if n % 2 == 0:
        continue

    jdg = True
    for i in range(3, int(n/2) + 1, 2):
        if n % i == 0:
            jdg = False
            break
    if jdg:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
c=0
n=int(input())
for _ in range(n):
 x=int(input())
 for i in range(2,x):
  if x%i==0:c+=1;break
print(n-c)

Submission status: Time Limit Exceeded

Solution code:
c=0
n=int(input())
for _ in range(n):
 x=int(input())
 if x!=2 and x%2==0:c+=1;continue
 for i in range(3,x,2):
  if x%i==0:c+=1;break
print(n-c)

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
n = int(raw_input())
count = 0
for i in range(n):
    break_f = False
    j = 3
    num = int(raw_input())
    if (num < 2):
        continue
    elif (num == 2):
        count += 1
        continue
    elif (num % 2 == 0):
        continue
    while j < num:
        if (num % j == 0):
            j += 2
            break_f = True
            break
        j += 2
    if break_f == True:
        continue
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def hoge(z):
    yuki = 0
    for i in range(2, z):
        if z % i == 0:
            yuki += 1
        if yuki:
            return False
    return True

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

Submission status: Time Limit Exceeded

Solution code:
def prime_numbers(numbers):
    total = 0
    for n in numbers:
        for i in range(2, n):
            if n % i == 0:
                break
        else:
            total += 1
    return total

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

Submission status: Time Limit Exceeded

Solution code:
def isprime(n):
    if n < 2: return 0
    elif n == 2: return 1

    if n % 2 == 0: return 0

    for i in range(3, n, 2):
        if n % i == 0 : return 0

    return 1

N = int(input())
n = [isprime(int(input())) for i in range(N)].count(1)

print(n)

Submission status: Time Limit Exceeded

Solution code:
def isprime(n):
    if n < 2: return 0
    elif n == 2: return 1

    if n % 2 == 0: return 0

    for i in range(3, n, 2):
        if n % i == 0 : return 0

    return 1

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

a = [i for i in n if isprime(i)]

print(len(a))

Submission status: Time Limit Exceeded

Solution code:
def main():
    alist = []
    for _ in range(int(input())):
        alist.append(int(input()))
    
    def is_prime(n):
        if n<=1:
            return False
        for i in range(2, n):
            if n % i == 0:
                return False
        return True
    
    result = sum(is_prime(n) for n in alist)
    print(result)

main()

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt, floor, ceil

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

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

        if n <= 1 or n % 2 == 0:
            return False

        # n = ceil(sqrt(n))
        for i in range(3, n, 2):
            if n % i*i == 0:
                return False
        return True

    result = sum([is_prime(n) for n in alist])
    print(result)

main()

Submission status: Time Limit Exceeded

Solution code:
cnt = 0
for i in range(int(input())):
    x = int(input())
    flg = False # なんらかの数で割り切れるかどうか
    if x == 1:
        continue
    if x == 2:
        cnt += 1
        continue
    for k in range(2, x):
        if not(x % k):
            flg = True
            break
    if not flg:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import math

def is_prime(x):
    if x == 1 : return False
    else : return all([x%i != 0 for i in range(2,int(math.sqrt(x)+1))])



if __name__ == '__main__' :
    N = int(input())
    count = 0
    for i in range(N):
        count += is_prime(int(input()))
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
  t = 2
  while n > t:
    if n % t == 0: return 0
    t += 1
  return 1

c = 0
for _ in range(int(input())):
  c += is_prime(int(input()))
print(c)

Submission status: Time Limit Exceeded

Solution code:
def is_prime(n):
  ps = [2, 3, 5, 7, 11, 13, 17]
  for p in ps:
    if n == p: return 1
    if n % p == 0: return 0
  t = 19
  while n > t:
    if n % t == 0: return 0
    t += 2
  return 1

c = 0
for _ in range(int(input())):
  c += is_prime(int(input()))
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[0]*n
count=0
for i in range(0,n):
    flag=1
    a[i]=int(input())
    for j in range(2,a[i]):
        if a[i]%j==0:
            flag=0
    if flag==1:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=[0]*n
for i in range(n):
	x[i]=int(input())
cnt=0
cnt2=0
for i in range(n):
	for j in range(1,x[i]+1):
		if x[i]%j==0:
			cnt+=1
	if cnt==2:
		cnt2+=1
	cnt=0

print(cnt2)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
a=[]
c=0.0
for i in range(n):
  a.append(input())
cnt=0
b=[int(i) for i in a]
for i in range(n):
    if b[i]==2:
      cnt+=1
    for j in range(2,b[i]):
      if b[i]%j==0:
        break
      if b[i]-j==1:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#16D8101023J 久保田凌弥 kubotarouxxx python3

a=int(input())
A=[0]*a
x=0
for i in range(a):
 A[i]=int(input())
 for j in range(1,A[i]):
  if A[i]==2:
    x+=1
    continue
  if j==1:
   continue
  elif (A[i]%j)==0:
   break
  elif j==(A[i]-1):
   x+=1
   
print(x)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
c=0
for j in range(n):
    x=int(input())
    for i in range(2,x+1):
        if x>i and x%i==0:
            break
        elif i==x and x%i==0:
            c+=1

print(c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
c=0
for j in range(n):
    x=int(input())
    for i in range(2,x+1):
        if x>i and x%i==0:
            break
        elif i==x and x%i==0:
            c+=1
            break

print(c)

Submission status: Time Limit Exceeded

Solution code:
import math

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

print(c)

Submission status: Time Limit Exceeded

Solution code:
def sosu(x):
	c=0
	for i in range(2,x):
		if x%i==0:
			c=c+1
	if c==0:
		return True
	else:
		return False
cnt=0
m=[]
n=int(input())
for i in range(n):
	o=int(input())
	m.append(o)
	if sosu(m[i]):
		cnt=cnt+1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def prime(x):
	c=0
	for i in range(2,x):
		if x%i==0:
			c=c+1
	if c==0:
		return True
	else:
		return False
cnt=0
m=[]
n=int(input())
for i in range(n):
	o=int(input())
	m.append(o)
	if prime(m[i]):
		cnt=cnt+1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:

def is_prime(x):
    if x == 2:
        return True
    else:
        if 2 ** (x-1) % x == 1:
            return True
        else:
            return False

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

    print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
import math

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


def is_prime(n):
    if (n == 2):
        return True
    elif (n % 2 == 0):
        return False
    else:
        for i in range(3, int(n / 2), 2):
            if n % i == 0:
                return False

    return True

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(N):
    a.append(int(input()))


count = 0
Sosu = True

for i in range(0,N):
    Sosu = True
    for j in range(2,a[i]):
        if a[i] % j == 0:
            Sosu = False
            break
        else :
            pass
    if Sosu :
        count+=1
    else:
        pass


print(count)

Submission status: Time Limit Exceeded

Solution code:
import math


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

m=int(input())
cnt=0
for i in range(m):
    n=int(input())
    if isprimer(n)==True:
        cnt=cnt+1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def divisor(num):
    for i in range(2, num):
        if num % i == 0:
            return False

    return True



N = int(input())
cnt = 0
for itr in range(N):
    num = int(input())
    if divisor(num):
        cnt = cnt + 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:

def divisor(num):
    for i in range(2, num):
        if i %2 == 0 and i != 2:
            continue
            
        if num % i == 0:
            return False

    return True



N = int(input())
cnt = 0
for itr in range(N):
    num = int(input())
    if divisor(num):
        cnt = cnt + 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:


def divisor(num):
    for i in range(2, num):
        if i %2 == 0 and i != 2:
            continue

        if num % i == 0:
            return False

    return True



N = int(input())
cnt = 0
for itr in range(N):
    num = int(input())
    if divisor(num):
        cnt = cnt + 1

print(cnt)

Submission status: Time Limit Exceeded

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

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

    cache = [2]
    primes = list(filter(lambda a: is_prime(a, cache), inputs))
    print(len(primes))

def is_prime(a, primes):
    if a == 2:
        return True
    for p in primes:
        if a % p == 0:
            return False
    for b in range(max(primes), a // 2):
        if any(map(lambda p: b % p != 0, primes)):
            primes.append(b)
        if a % b == 0:
            return False
    return True

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, n // 2 + 1):
        if n % i == 0:
            return False
    return True


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

Submission status: Time Limit Exceeded

Solution code:
def isPrime(n):
    if n <= 2:
        return n == 2
    if (n % 2 == 0):
        return False
    for i in range(2, n // 2 + 1):
        if n % i == 0:
            return False
    return True


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

Submission status: Time Limit Exceeded

Solution code:
def isPrime(n):
    if n <= 2:
        return n == 2
    if (n % 2 == 0):
        return False
    for i in range(3, n // 2 + 1, 2):
        if n % i == 0:
            return False
    return True


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

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    if (n==2):
        return True
    elif(n == 1):
        return False
    else:
        pr = [2]
        for i in range(3,n):
            c = 0
            for p in pr:
                if (i % p != 0):
                    c = c + 1
            if (c == len(pr)):
                pr.append(i)
        cc = 0        
        for p in pr:
            if(n%p != 0):
                cc = cc + 1
    
    if(cc == len(pr)):
        return True
    else:
        return False
        
    
N = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    if (n==2):
        return True
    elif(n == 1):
        return False
    else:
        pr = [2]
        for i in range(3,n):
            c = 0
            for p in pr:
                if (i % p != 0):
                    c = c + 1
            if (c == len(pr)):
                if n%i == 0:
                    return False 
                    break
                pr.append(i)
        cc = 0        
        for p in pr:
            if(n%p != 0):
                cc = cc + 1
            elif(n%p == 0):
                return False
                break
    
    if(cc == len(pr)):
        return True
    else:
        return False
        
    
N = int(input())

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mlist = []
for i in range(n):
    m = int(input())
    mlist.append(m)
mlist.sort()
plist = [2]
for i in range(3,mlist[-1]+1):
    count = 0
    for k in plist:
        if (i%k != 0):
            count += 1
        else:
            break
    if (count == len(plist)):
        plist.append(i)
count = 0
for i in mlist:
    if(i in plist):
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mlist = []
for i in range(n):
    m = int(input())
    mlist.append(m)
mlist.sort()
plist = [2]
count = 0
j = 2
for i in mlist:
    if (i in plist):
        count += 1  
    else:
        for k in range(j+1, i+1):
            c = 0
            for p in plist:
                if (k % p != 0):
                    c += 1
                else : 
                    break
            if (c == len(plist)):
                plist.append(k)   
                if (k == i):
                    count += 1
    j = i
print(count)

Submission status: Time Limit Exceeded

Solution code:
def isPrime(n):
    if n == 1:
        return False
    elif n == 2 or n == 3:
        return True
    else:
        for i in range(2, n//2+1):
            if n % i == 0:
                return False
        return True


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

Submission status: Time Limit Exceeded

Solution code:
class PrimeChecker(object):
    def __init__(self):
        self.primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53]
    
    def isPrime(self, n):
        if n in self.primes:
            return True
        elif n < 53:
            return False
        else:
            for i in self.primes:
                if n % i == 0:
                    return False
            for i in range(53, n//2, 2):
                if n % i == 0:
                    return False
            self.primes.append(n)
            return True


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

Submission status: Time 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*i<=x:
        if x%i==0:
            return False
    return True

while True:
    try:
        n = int(input())
    except:
        break
    ans=0
    for i in range(n):
        num=int(input())
        if isprime(num):
            ans+=1
    print(ans)

Submission status: Time 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*i<=x:
        if x%i==0:
            return False
    return True

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

Submission status: Time Limit Exceeded

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

Submission status: Time 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 xrange(3, v//2, 2):
            if v % i == 0:
                cnt -= 1
                break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = input()
s = 0
while n > 0:
	n -= 1
	a = input()
	count = 0
	for i in range(1, int(a**0.5)+1):
		if (a % i) == 0:
			count += 1
	if count == 1:
		s += 1
print s

Submission status: Time Limit Exceeded

Solution code:
n = input()
s = 0
while n > 0:
	n -= 1
	a = input()
	if sum(map(lambda x: a%x==0, range(1, int(a**0.5)+1))) == 1:
		s += 1
print s

Submission status: Time Limit Exceeded

Solution code:
n = input()
s = 0
while n > 0:
	n -= 1
	a = input()
	count = 0
	for i in range(1, int(a**0.5)+1):
		count += (a%i==0)
	if count == 1:
		s += 1
	#if sum(map(lambda x: a%x==0, range(1, int(a**0.5)+1))) == 1:
	#	s += 1
print s

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time 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 xrange(3,int(x*0.5+1),2):
            if x % j == 0: break
        else: count += 1
print count

Submission status: Time Limit Exceeded

Solution code:
def prime(x):
    if x == 2: return True
    elif x % 2 == 0: return False
    else:
        for j in xrange(3,int(x*0.5+1),2):
            if x % j == 0: return False
        else: return True

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def isprime(x):
    if x == 2: return True
    if x % 2 == 0: return False
    for i in range(3, x, 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: Memory Limit Exceeded

Solution code:
from sys import stdin

n = int(stdin.readline().rstrip())
nNum = [int(stdin.readline().rstrip()) for i in range(n)]
nNum.sort(reverse=True)

def sieveOfEratos(n):
    isPrime = [False] * 2 + [True] * (n-1)
    for i in range(2, n+1):
        if i * i >= n+1:
            break
        elif isPrime[i]:
            for j in range(i*i, n+1, i):
                isPrime[j] = False

    return isPrime

isPrime = sieveOfEratos(nNum[0])
print(len([True for i in nNum if isPrime[i] == True]))

Submission status: Memory Limit Exceeded

Solution code:
def get_sieve_of_eratosthenes(x):
    a = [True] * (x + 1)
    a[0] = a[1] = False
    y = 2
    i = 0
    while i <= x ** 1/2:
        if a[i]:
            j = i + 1
            while j <= x:
                if j % i == 0:
                    a[j] = False
                j += 1
        i += 1
    res = list()
    for i in range(x + 1):
        if a[i]:
            res.append(i)
    return res


n = int(input())
pn = get_sieve_of_eratosthenes(10**8)
cnt = 0
for i in range(n):
    x = int(input())
    if x in pn:
        cnt += 1
print(cnt)

Submission status: Memory Limit Exceeded

Solution code:
def get_sieve_of_eratosthenes(x):
    prime = [2]
    data = [i + 1 for i in range(2, x, 2)]
    while True:
        p = data[0]
        prime.append(p)
        if p ** 2 > n:
            return prime + data
        data = [e for e in data if e % p != 0]


n = int(input())
pn = get_sieve_of_eratosthenes(10**8)
cnt = 0
for i in range(n):
    x = int(input())
    if x in pn:
        cnt += 1
print(cnt)

Submission status: Memory Limit Exceeded

Solution code:
def get_sieve_of_eratosthenes(x):
    data = [True] * (x + 1)
    data[0] = data[1] = False
    i = 2
    while i ** 2 <= x:
        if data[i]:
            for j in range(i + 1, x + 1):
                if j % i == 0:
                    data[j] = False
        i += 1
    return data


pn = get_sieve_of_eratosthenes(10 ** 8)
n = int(input())
cnt = 0
for i in range(n):
    a = int(input())
    if pn[a]:
        cnt += 1
print(cnt)

Submission status: Memory Limit Exceeded

Solution code:
p=[1]*10**8

i=2
while i*i<10**8:
    if p[i]:
        j=i+i
        while j<10**8:
            p[j]=0
            j+=i
    i+=1
count=0
for i in range(int(input())):
    if p[int(input())]==1:
        count+=1
        
print(count)

Submission status: Memory Limit Exceeded

Solution code:
# https://qiita.com/fantm21/items/5e270dce9f4f1d963c1e
def get_sieve_of_eratosthenes(n):
    import math
    prime = []
    limit = math.sqrt(n)
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    count = 0
    in_data_number = int(input())
    in_data = [0]*in_data_number
    mod_zero_cnt = 0
    prime_number = 0
    for i in range(in_data_number):
        mod_zero_cnt = 0
        in_data[i] = int(input())
    in_data_max = max(in_data)
    prime_number = get_sieve_of_eratosthenes(in_data_max)
    for i in range(in_data_number):
        if in_data[i] in prime_number:
            count +=1;
    print(count)
if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
def seive(num):
    nums = [1] * num
    nums[0], nums[1] = 0, 1
    for i in range(1, int(num ** 0.5) + 1):
        if nums[i-1] == 0:
            continue
        else:
            j = i * 2
            while j <= num:
                nums[j-1] = 0
                j += i

    res = []
    for n in range(len(nums)):
        if nums[n] == 1:
            res.append(n + 1)
    return res

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

res = seive(max(nums))
ans = 0
for n in nums:
    if n in res:
        ans += 1

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
def isPrime(n):
    if (n < 4):
        return True
    for i in range(2, (n / 2) + 1):
        if (0 == (n % i)):
            return False
    return True

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

main()

Submission status: Memory Limit Exceeded

Solution code:
c=input()
pc=0
for _ in range(c):
    n=input()
    for i in range(2, n):
        if n % i == 0:
            break
    else:
        pc+=1
print pc

Submission status: Memory Limit Exceeded

Solution code:
import os

c=input()
pc=0
for _ in range(c):
    n=input()
    for i in range(2, n):
        if n % i == 0:
            break
    else:
        pc+=1
    del n
print pc

Submission status: Memory Limit Exceeded

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


n = int( raw_input( ) )
nums = []
cnt = 0
while True:
	nums.append( int( raw_input( ) ) )
	cnt += 1
	if cnt == n:
		break

cnt = 0
for i in range( n ):
	if isPrime( nums[i] ):
		cnt += 1

print( cnt )

Submission status: Memory Limit Exceeded

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


n = int( raw_input( ) )
nums = []
cnt = 0
while True:
	nums.append( int( raw_input( ) ) )
	cnt += 1
	if cnt == n:
		break

cnt = 0
for i in range( n ):
	
	if isPrime( nums[i] ):
		cnt += 1

print( cnt )

Submission status: Memory Limit Exceeded

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


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

print( cnt )

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/env python3
from math import sqrt


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

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

Submission status: Memory Limit Exceeded

Solution code:
import sys

num_list = []

for line in sys.stdin.readlines():
    num_list.append(int(line.strip()))

num_list.remove(num_list[0])

count = 0

for num in num_list:
    flag = 0
    if num != 1:
        for i in range(2, num-1):
            if num % i == 0:
                flag = 1
                break
    if flag == 0:
        count += 1

print count

Submission status: Memory Limit Exceeded

Solution code:
import sys

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, num-1):
            if num % i == 0:
                flag = 1
                break
        if flag == 0:
            count += 1

print count

Submission status: Memory Limit Exceeded

Solution code:
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 == 2:
        count += 1
    elif num % 2 == 0 or num == 0 or num == 1:
        pass
    else:
        count += 1
        for i in range(3, num/2, 2):
            if num % i == 0:
                count -= 1
                break
print count

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:
    c2 = 0
    for j in range(2,v):
        if v%float(j) == 0:
            c2 = 1
            break
        else:
            pass
    if c2 != 1:
        c += 1



print c

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:
    a = 0
    for j in range(2,v):
        if v%float(j) == 0:
            a = 1
            break
    if a != 1:
        c += 1



print c