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: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
#i = 2
N=int(raw_input())
ans=0
a=3
for i in range(N):
    x=int(raw_input())
    if x<2: pass
    elif x==2: ans+=1
    elif x%2==0: pass
    else:
        a=3
        while a**2 <= x:
            if x%a==0: pass
            a+=2
        ans+=1

print (ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
cnt=0
sute=0
N=int(raw_input())
while sute==0:
    for j in range(N):
        x=int(raw_input())
        if x<2:
            pass
        elif x==2:
            cnt+=1
        elif x%2==0:
            pass
        else:
            a=3
            while a**2<=x:
                if x%a==0:
                    pass
                a+=2
            cnt+=1
#        print j
#        print cnt
        if j==N-1:
            sute+=1
    sute+=1


print cnt

Submission status: Wrong Answer

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):
    if num == 2: return True
    start = 2
    for i in cached:
        if num % i == 0:
            return False
    start = cached[-1]
    for i in range(start,num):
        if num % i == 0:
            return False
    cached.append(num)
    return True

main()

Submission status: Wrong Answer

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):
    print "cached:{0}".format(" ".join(map(str,cached)))
    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: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import math
r = 10000001
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)]
  
n = int(raw_input())
for i in range(n):
    m = int(raw_input())
    print sum(p[:n])

Submission status: Wrong Answer

Solution code:
import math
r = 10000001
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)]
   
n = int(raw_input())
ans = 0
for i in range(n):
    m = int(raw_input())
    ans += p[m-1]

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    import sys
    import math
    N = int(sys.stdin.readline().strip())
    numbers = []
    for i in range(N):
        numbers.append(int(sys.stdin.readline().strip()))
    maxNum = max(numbers)
    for i in range(2, int(math.sqrt(maxNum)) + 1):
        for j, n in enumerate(numbers):
            if n%i == 0:
                del numbers[j]
    print len(numbers)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    import sys
    import math
    N = int(sys.stdin.readline().strip())
    numbers = []
    for i in range(N):
        n = int(sys.stdin.readline().strip())
        if n > 1:
            numbers.append(n)
    maxNum = max(numbers)
    for i in range(2, int(math.sqrt(maxNum)) + 1):
        for j, n in enumerate(numbers):
            if n%i == 0:
                del numbers[j]
    print len(numbers)

Submission status: Wrong Answer

Solution code:
import math

def isprime(x):
    if x == 2: return True
    if x % 2 == 0: return False
    for i in range(3, math.ceil(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 isprime(x): count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
numberOfInput=int(input())
primeNumbers=[]

def isPrime(researchNumber):
    for devidedBy in range(1,researchNumber+1):
        if researchNumber%devidedBy==0 and devidedBy!=1 and devidedBy!=researchNumber:
            break
        elif researchNumber%devidedBy==0 and devidedBy==researchNumber:
            primeNumbers.append(researchNumber)


#----------------------------------main------------------------------------------
while numberOfInput>0:
    researchNumber=int(input())
    if researchNumber==1:
        pass
    else:
        isPrime(researchNumber)
    numberOfInput-=1
print(len(primeNumbers))

Submission status: Time Limit Exceeded

Solution code:
numberOfInput=int(input())
primeNumbers=0

while numberOfInput>0:
    researchNumber=int(input())
    if researchNumber==1:
        pass
    else:
        for devidedBy in range(1,researchNumber+1):
            if researchNumber%devidedBy==0 and devidedBy!=1 and devidedBy!=researchNumber:
                break
            elif researchNumber%devidedBy==0 and devidedBy==researchNumber:
                primeNumbers+=1
    numberOfInput-=1

print(primeNumbers)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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


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

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

Submission status: Time Limit Exceeded

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:
        if n%i == 0:
            return 0
        else:  
            i += 2
    return 1

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

Submission status: Time Limit Exceeded

Solution code:
def primeq(x):
    if x==1:return False
    for i in range(2,x):
        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: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    primelist = []
    for _ in range(n):
        x = int(input())
        if isprime(x) == 1:
            primelist.append(x)
    print(len(primelist))

def isprime(x: int):    
    yesno = 1
    for y in range(2, x):
        if gcd(x, y) != 1:
            yesno = 0
            break
    return yesno

def gcd(x, y):    
    # x > y となるように並べ替え
    if x < y:
        (x, y) = (y, x)
    return x if y == 0 else gcd(y, x%y)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    primelist = []
    for _ in range(n):
        x = int(input())
        if isprime(x) == 1:
            primelist.append(x)
    print(len(primelist))

def isprime(x: int):    
    if x == 2:
        return 1
    elif x % 2 == 0:
        return 0
    else:        
        yesno = 1
        for y in range(3, x, 2):
            # 偶数は最初に除外するので、奇数で割れるかだけ見ていく
            if x % y == 0:
                yesno = 0
                break
    return yesno

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# とても時間がかかる

def main():
    n = int(input())
    count = 0
    for _ in range(n):
        x = int(input())
        if isprime(x) == 1:
            count += 1
    print(count)

def isprime(x: int):    
    if x == 2:
        return 1
    elif x % 2 == 0:
        return 0
    else:        
        yesno = 1
        for y in range(3, x//2, 2):
            # 偶数は最初に除外するので、奇数で割れるかだけ見ていく
            if x % y == 0:
                yesno = 0
                break
    return yesno

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    count = 0
    for _ in range(n):
        x = int(input())
        if isprime(x) == 1:
            count += 1
    print(count)

def isprime(x: int):    
    if x == 2:
        return 1
    elif x % 2 == 0:
        return 0
    else:        
        for y in range(3, x, 2):
            # 偶数は最初に除外するので、奇数で割れるかだけ見ていく
            if x % y == 0:
                return 0
    return 1

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
x = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
x = int(input())

count = 0
for i in range(0, x):
    a =  int(input())
    if a % 2 == 0 and a != 2:
        count += 1
    elif a % 3 == 0 and a != 3:
        count += 1
    else:
        c =int((a + 1) / 2)
        for j in range ( 3,  c-1 ):
            if a % j == 0:
                count += 1
                break;
        
print(x-count)

Submission status: Time Limit Exceeded

Solution code:
x = int(input())

count = 0
for i in range(0, x):
    a =  int(input())
    if a == 2 or a == 3:
        count += 0
    elif a == 4:
        count += 1
    c =int(a / 2)
    for j in range ( 2,  c ):
        if a % j == 0:
             count += 1
             break;
        
print(x-count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
cnt = 0
for i in range(n):
    x = int(input())
    j = 2
    flag = 0
    while j <= x ** 1/2:
        if x % j == 0:
            flag = 1
            break
        j += 1
    if flag == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

count = 0

for i in range(n):
  check = True
  
  key = int(input())

  for i in range(2,key):
    if key % i == 0:
      check = False
    
  if check:
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# https://qiita.com/asksaito/items/76b71602dd956b79dbf7
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())
    
    for j in range(1,int(in_data[i]/2)+1):
        if in_data[i] != 2 and in_data[i] % 2 == 0:
            break
        mod_result = in_data[i] % j
       # print("in_data={}".format(in_data))
        #print("division={}".format(j))
        if mod_result == 0:
            mod_zero_cnt += 1
            #print("mode_zero_cnt: {}".format(mod_zero_cnt))
    if mod_zero_cnt == 1:
        prime_number += 1
print(prime_number)

Submission status: Time Limit Exceeded

Solution code:
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValuseError("n is more than 2")
    data = [i for i in range(2, n+1)]
    for d in data:
        data = [x for x in data if(x==d or x % d !=0)]
    return data

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

Solution code:

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

	chknum = int(input())

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    ans = 0
    for i in range(n):
        x = int(input())
        flag = True
        for j in range(2, x):
            if x % j == 0:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def gcd ( ax, ay):
    x = ax
    y = ay
    while (True):
        if x < y :
            tmp = x
            x = y
            y = tmp
        x=x %y
        if x == 0:
            return y
        elif x == 1:
            return 1

def check_pn(num):
    count = 0
    for i in range(2, num):
        if gcd(i, num) != 1:
            return False

    return True


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

count = 0
for data in listdata:
    count += check_pn(data)

print(count)

Submission status: Time Limit Exceeded

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

def gcd ( ax, ay):
    x = ax
    y = ay
    while (True):
        if x < y :
            tmp = x
            x = y
            y = tmp
        x=x %y
        if x == 0:
            return y
        elif x == 1:
            return 1

def check_pn(num):
    count = 0
    for i in range(2, num):
        if gcd(i, num) != 1:
            return False

    return True


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

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

print (n)

Submission status: Time Limit Exceeded

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

def gcd ( ax, ay):
    x = ax
    y = ay
    while (True):
        if x < y :
            tmp = x
            x = y
            y = tmp
        x=x %y
        if x == 0:
            return y
        elif x == 1:
            return 1

def check_pn(num):
    count = 0
    for i in range(2, int((num)/2)+1):
        if gcd(i, num) != 1:
            return False

    return True


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

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

print (n)

Submission status: Time Limit Exceeded

Solution code:
def prime_number(num):
    if num == 2 :
        return 1
    elif (num%2)==0:
        return 0
    elif num > 2:
        for i in range(3,num-1,2):
            if (num % i) == 0:
                return 0
        return 1

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

Submission status: Time Limit Exceeded

Solution code:
N = input()
c = 0
p = [0 for i in range(N)]
for i in range(0,N):
	p[i] = input()
for i in range(N):
	j = p[i]-1
	while(j > 1):
		if(p[i]%j == 0):break
		j -= 1
	if(j == 1):
		c += 1
print c

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())

i, c = 0, 0

while(i<n):
    a = int(raw_input())

    if a==2:
        c+=1

    for x in xrange(2, a):
        if a%x==0:
            break

        if a-1==x and a%x!=0:
            c+=1

    i+=1
print c

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())

c = 0

pn = []

for i in xrange(n):

    a = int(raw_input())

    if a==2:
        c+=1
        pn.append(a)
        continue

    for x in pn:
        if a==x:
            c+=1
            pn.append(a)
            break

    for x in xrange(2, a):
        if a%x==0:
            break

        if a-1==x and a%x!=0:
            c+=1

print c

Submission status: Time Limit Exceeded

Solution code:
def euclid(m,n):
    while m%n>0:
        m,n=n,m%n
    else:
        return n

def isprime_euclid2(N):
    if N<1:
        print 'N>2'
    elif N==2:
        return True
        
    euclid_list=[]
    for k in range(1,int(round(math.sqrt(N)))+1):
        euclid_list.append(euclid(N,k))
    temp=set(euclid_list)
    if len(temp)==1:
        return True
    else:
        return False  
           
import math
while True:
    try:
        n = int(raw_input())
        total = 0
        for k in range(n):
            if isprime_euclid2(int(raw_input())):
                total +=1
        print total
    except EOFError:
        break

Submission status: Time Limit Exceeded

Solution code:
import fractions

def prime_generator(upper):
    primes = [2, 3]
    yield 2
    yield 3

    for i in range(5, upper+1, 2):
        is_prime = True
        for p in primes:
            if p ** 2 > i:
                break
            if i % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
            yield i

if __name__ == '__main__':
    n = int(input())
    inputs = [int(input()) for _ in range(n)]
    inputs.sort()
    inputs.append(10**8+1)
    index = 0
    cnt = 0

    for p in prime_generator(inputs[n-1]):
        if index >= n:
            break

        while p > inputs[index] and index < n:
            index += 1

        if p == inputs[index]:
            while p == inputs[index] and index < n:
                index += 1
                cnt += 1
            continue

        if p < inputs[index]:
            continue

    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import functools
def divise(n, divisor):
    if n % divisor == 0 and n != divisor:
        return 0
    else:
        return n

if __name__ == '__main__':
    number = input()
    origin = [int(input()) for _ in range(number)]

    divised = origin

    hoge = []
    for i in range(number):
        hoge.append(True)

    for i in range(2, max(origin)+1):
        divised = list(map(functools.partial(divise, divisor=i), divised))

    for j in range(number):
        if divised[j] == 0:
            hoge[j] = False

    cnt = 0
    for b in hoge:
        if b:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from functools import lru_cache
from itertools import count, takewhile


def prime():
    prime = []

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


@lru_cache(maxsize=None)
def isPrime(n):
    if n < 2:
        return False
    for p in takewhile(lambda x: x * x <= n, prime()):
        if n % p == 0:
            return False
    return True

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

N=int(input())

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

Submission status: Time Limit Exceeded

Solution code:
def judgePrime(n):
  result = True
  for i in xrange(2, n):
    if n % i == 0:
      result = False
      break
  return result

n = int(raw_input())
count = 0

for i in xrange(n):
  if judgePrime(int(raw_input())):
    count += 1

print count

Submission status: Time Limit Exceeded

Solution code:
def judgePrime(n):
  result = True
  for i in xrange(2, n):
    if n % i == 0:
      result = False
      break
  return result

def getPrimeNumFromList(list):
  count = 0
  for i in xrange(len(list)):
    target = 0
    if i == 0:
      target = list[0]
      if judgePrime(target):
        count += 1
      else:
        pass

  return count

n = int(raw_input())
list = []
for i in xrange(n):
  list.append(int(raw_input()))
list.sort()

count = 0
for i in xrange(n):
  if judgePrime(list[i]):
    count += 1
print count
# print getPrimeNumFromList(list)

Submission status: Time Limit Exceeded

Solution code:
def judgePrime(n):
  result = True
  for i in xrange(2, int(round(n))):
    if n % i == 0:
      result = False
      break
  return result

def getPrimeNumFromList(list):
  count = 0
  for i in xrange(len(list)):
    target = 0
    if i == 0:
      target = list[0]
      if judgePrime(target):
        count += 1
      else:
        pass

  return count

n = int(raw_input())
list = []
for i in xrange(n):
  list.append(int(raw_input()))
list.sort()

count = 0
for i in xrange(n):
  if judgePrime(list[i]):
    count += 1
print count

# print judgePrime(list[len(list) - 1])

Submission status: Time Limit Exceeded

Solution code:
def judgePrime(n):
  result = True
  for i in xrange(2, int(round(n))):
    if n % i == 0:
      result = False
      break
  return result

def getPrimeNumFromList(list):
  count = 0
  for i in xrange(len(list)):
    target = 0
    if i == 0:
      target = list[0]
      if judgePrime(target):
        count += 1
      else:
        pass

  return count

n = int(raw_input())
list = []

for i in xrange(n):
  list.append(int(raw_input()))
list.sort()

prime_list = []
all_list = range(2, list[len(list) - 1] + 1)

while True:
  v = all_list.pop(0)
  prime_list.append(v)
  # print "all_list : "
  # print all_list
  # print "prime_list : "
  # print prime_list
  for i in xrange(len(all_list)):
    if i >= len(all_list):
      break
    elif all_list[i] % v == 0:
      all_list.pop(i)
      i -= 1
  if len(all_list) == 0:
    break
  elif prime_list[len(prime_list) - 1] ^ 2 >= all_list[len(all_list) - 1]:
    prime_list.append(all_list)
    break

count = 0
for i in xrange(len(prime_list)):
  if prime_list[i] in list:
    count += 1

print count

Submission status: Time Limit Exceeded

Solution code:
import pdb

def judgePrime(n):
  result = True
  for i in xrange(2, int(round(n))):
    if n % i == 0:
      result = False
      break
  return result

def getPrimeNumFromList(list):
  count = 0
  for i in xrange(len(list)):
    target = 0
    if i == 0:
      target = list[0]
      if judgePrime(target):
        count += 1
      else:
        pass

  return count

n = int(raw_input())
list = []

for i in xrange(n):
  list.append(int(raw_input()))
list.sort()

prime_list = []

while True:
  v = list.pop(0)
  if not judgePrime(v):
    continue
  prime_list.append(v)
  # print "list : "
  # print list
  # print "prime_list : "
  # print prime_list
  i = 0
  while True:
    # print "i = " + str(i)
    if i >= len(list):
      break
    elif list[i] % v == 0:
      list.pop(i)
      # print "i = " + str(i) + ", list: "
      # print list
    else:
      i += 1
  if len(list) == 0:
    break
  elif prime_list[len(prime_list) - 1] ^ 2 >= list[len(list) - 1]:
    prime_list.append(list)
    break

print len(prime_list)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

count = 0

num_list = []

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

num_list.remove(num_list[0])

for num in num_list:
        flag = 0
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                flag = 1
    #            break
        if flag == 0:
            count += 1

print count

Submission status: Time Limit Exceeded

Solution code:
import sys

lines = sys.stdin.readlines()

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

c = 0
for i,v in enumerate(lst):
    if len([j for j in range(1,v+1) if v%float(j) == 0]) == 2:
        c += 1
    else:
        pass


print c

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

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 j == math.sqrt(v):
            break
    if m == v:
        c += 1



print c

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

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 and math.sqrt(v) == j:
            break
        elif v%float(j) == 0:
            m = j
            break
    if m == v:
        c += 1



print c

Submission status: Time Limit Exceeded

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

def is_prime(n):
  for m in range(2, n):
    if n % m == 0:
      return False
  return True

print(len([n for n in ns if is_prime(n)]))

Submission status: Time Limit Exceeded

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

primes = set()
def is_prime(n):
  if n in primes:
    return True

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

print(len([n for n in ns if is_prime(n)]))

Submission status: Time Limit Exceeded

Solution code:
N = input()
prime = 0

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

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

print prime

Submission status: Time Limit Exceeded

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

primes = [True]*n
for d in range(2,10001):
    for i in range(n):
        if d!=a[i] and a[i]%d==0:
            primes[i] = False

print sum(primes)

Submission status: Time Limit Exceeded

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

nprimes = 0
a = sorted(a)
while True:
    for d in range(2,10001):
        if d==a[0]:
            nprimes+=1
            del a[0]
            break
        elif a[0]%d==0:
            del a[0]
            break
    if len(a) <= 0:
        break

print nprimes

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

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

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

count = 0
for j in n:
    if Is_prime(j):
        count += 1

print (count)

Submission status: Time Limit Exceeded

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

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

count = 0
for j in n:
    if Is_prime(j):
        count += 1

print (count)

Submission status: Time Limit Exceeded

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

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

count = 0
for j in n:
    if Is_prime(j):
        count += 1

print (count)

Submission status: Time Limit Exceeded

Solution code:
import math

def prime_numbers(x):
    i_a = list(range(2, x+1))
    p_a = list()
    e_a = math.sqrt(x)
    h = i_a[0]
    while h < e_a:
        h = i_a[0]
        p_a.append(h)
        for j in i_a:
            if j % h == 0:
                i_a.remove(j)
    p_a += i_a
    p_a.sort()
    return p_a

if __name__ == "__main__":
    n = int(input())
    n_s = list()
    for i in range(n):
        n_s.append(int(input()))

    pnums = prime_numbers(max(n_s))
    count = 0

    for i in n_s:
        if i in pnums:
            count += 1

    print(count)

Submission status: Time Limit Exceeded

Solution code:
a=input()
def ip(a):
    i=2
    while i**2<=a:
        if a%i==0:return False
    return True
b=0
for i in range(a):
    a=input()
    if ip(a):b+=1
print(str(b))

Submission status: Time Limit Exceeded

Solution code:
a=input()
def ip(a):
    i=2
    while i**2<=a:
        if a%i==0:return False
    return True
b=0
for i in range(a):
    c=input()
    if ip(c):b+=1
print(str(b))

Submission status: Time Limit Exceeded

Solution code:
a=input()
def ip(a):
    i=2
    while i**2<=a:
        if a%i==0:return False
    return True
b=0
for i in range(int(a)):
    c=input()
    if ip(int(c)):b+=1
print(str(b))