prime-testing-1

Given N numbers A[i], find the count of prime numbers.

Input Specifications:

The first line contains number of Test cases, T.
For each test case T,
    The first line contains N.
    N lines follow with A[1] to A[n]

Output Specifications

For every test case T, a count of the total number of prime numbers

Hint: 0 and 1 are not prime numbers

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 1000000
0 ≤ A[i] ≤ 1000
Register for IndiaHacksSAMPLE INPUT
1
5
45 
31
7
28
90

SAMPLE OUTPUT
2

Register for IndiaHacks

Source: hackerearth | Difficulty: EASY


Solutions:
import math
noOfTestCases = int(input())

def checkPrime(no):
	if(no == 0 or no == 1):
		return False
	start = 2
	end = int(math.sqrt(no))
	while(start<=end):
		if(no % start == 0):
			return False
		start += 1	
	return True	

def count(nos):
	c = 0
	for no in nos:
		if(checkPrime(no)):
			c += 1
	return c

for caseNo in range(1, noOfTestCases + 1):
	noOfElem = int(input())
	elements = []
	for n in range(1, noOfElem + 1):
		elements.append(int(input()))
	print(count(elements))	
		


def isPrime(n):
	if n in [2,3]:
		return True
	if n < 2 or n % 2 ==0 or n % 3==0:
		return False
	i, w = 5, 2
	while i * i <= n:
		if n % i == 0:
			return False
		i, w = i + w,  6 - w
	return True


for _ in range(eval(input())):
	toi = eval(input())
	cnt = 0
	while toi:
		toi -= 1
		if isPrime(int(input())):
			cnt +=1
	print(cnt)    


def prime(number):
	j=2
	if number<=1:
		return False
	q=int(number**0.5)+1
	while j<q:
		if number%j==0:
			return False
		j=j+1
	return True

for _ in range(eval(input())):
	count=0
	for i in range(eval(input())):
		a=eval(input())
		if prime(a):
			#print a
			count =count +1
	print(count)
	
	


import math
noOfTestCases = int(input())

def checkPrime(no):
	if(no == 0 or no == 1):
		return False
	start = 2
	end = int(math.sqrt(no))
	while(start<=end):
		if(no % start == 0):
			return False
		start += 1	
	return True	

def count(nos):
	c = 0
	for no in nos:
		if(checkPrime(no)):
			c += 1
	return c

for caseNo in range(1, noOfTestCases + 1):
	noOfElem = int(input())
	elements = []
	for n in range(1, noOfElem + 1):
		elements.append(int(input()))
	print(count(elements))	
		


import math
for _ in range(int(input())):
	n=eval(input())
	r=0
	for i in range(n):
		m=eval(input())
		if m==0 or m==1:
			continue
		c=0
		m1=int(math.sqrt(m))
		for j in range(2,m1+1):
			if m%j==0:
				c+=1
		if c==0:
			r+=1
	print(r)
				
		


def isprime(n):
	if n < 2: return False
	if n == 2: return True
	if n == 3: return True
	if n % 2 == 0: return False
	if n % 3 == 0: return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0: return False
		i += w
		w = 6 - w
	return True
for _ in range(int(input())):
	ans = 0
	for n in range(int(input())):
		if isprime(int(input())): ans += 1
	print(ans)	
	
	


def isprime(a):
	if a==1 or a==0:
		return False
	if a==3 or a==2:
		return True
	for i in range(2, int(a**0.5)+1):
		if a%i==0:
			return False
	return True	

t=eval(input())
for k in range(t):
	n=eval(input())
	s=[]
	for i in range(n):
		s.append(eval(input()))
	count=0
	for i in range(n):
		if (isprime(s[i])):
			count+=1
	print(count)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t=int(input())

h=[]
a=[True]*1001
for i in range(2,1001):
	if a[i]:
		h.append(i)
		for m in range(2*i,1001,i):
			a[m]=False


for i in range(0,t):
	m1=int(input())
	count=0
	for i in range(0,m1):
		if int(input()) in h:
			count=count+1
	print(count)


'''
https://www.hackerearth.com/nit-calicut-codeburst-50/algorithm/prime-testing-1/
'''

T = int(eval(input()))
prime_number_set = set([2,3,5,7,11,13,17,19,23,29, 31,37,41,43,47,53,59,61,67,71, 73,79,83,89,97,101,103,107,109,113, 127,131,137,139,149,151,157,163,167,173, 179,181,191,193,197,199,211,223,227,229, 233,239,241,251,257,263,269,271,277,281, 283,293,307,311,313,317,331,337,347,349, 353,359,367,373,379,383,389,397,401,409, 419,421,431,433,439,443,449,457,461,463, 467,479,487,491,499,503,509,521,523,541, 547,557,563,569,571,577,587,593,599,601, 607,613,617,619,631,641,643,647,653,659, 661,673,677,683,691,701,709,719,727,733, 739,743,751,757,761,769,773,787,797,809, 811,821,823,827,829,839,853,857,859,863, 877,881,883,887,907,911,919,929,937,941, 947,953,967,971,977,983,991,997])

for tc in range(T) :
	N = int(eval(input()))
	sum = 0
	for n in range(N):
		t = int(eval(input()))
		if t in prime_number_set :
			sum += 1
	print(sum)



import math
noOfTestCases = int(input())

def checkPrime(no):
	if(no == 0 or no == 1):
		return False
	start = 2
	while(start<no):
		if(no % start == 0):
			return False
		start += 1	
	return True	

def count(nos):
	c = 0
	for no in nos:
		if(checkPrime(no)):
			c += 1
	return c

for caseNo in range(1, noOfTestCases + 1):
	noOfElem = int(input())
	elements = []
	for n in range(1, noOfElem + 1):
		elements.append(int(input()))
	print(count(elements))	
		


def is_prime(n):
	return all([(n%j) for j in range(2, int(n**0.5)+1)]) and n>1
t=eval(input(""))
while t>0:
	n=eval(input(""))
	c=0
	for i in range(n):
		num=eval(input(""))
		if is_prime(num):
			c+=1
	print(c)
	t-=1



import math
for _ in range(int(input())):
	n=eval(input())
	r=0
	for i in range(n):
		m=eval(input())
		if m==0 or m==1:
			continue
		c=0
		m1=int(math.sqrt(m))
		for j in range(2,m1+1):
			if m%j==0:
				c+=1
		if c==0:
			r+=1
	print(r)