CBOJ Exec Selection Contest 2 Problem 2 - Patryk and Primes

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 256M

Problem type

Patryk has always been fascinated by the field of number theory. As a result, he was given an array \(A\) of \(N\) positive intgers for his birthday for him to ponder upon. Curious, he wonders how many values in the array are prime numbers.

Although he is interested in number theory, he has no clue what prime numbers are! He then comes to you for help. Can you help Patryk?


The first line contains a single integer \(N\), representing the length of the array.

The second, and last, line will contain \(N\) space separated integers, representing the values of the array.


Output the number of elements that are prime numbers.


\(1 \le N \le 10^{5}\)

\(1 \le A_{i} \le 10^{5}\)

Sample Input 1

1 3 10 124 3

Sample Output 1


Explanation for Sample Output 1

\(1\) is not a prime number, by definition.

\(3\) is a prime number, since it is divisible only by \(1\) and itself.

\(10\) is divisible by both \(5\) and \(2\), so it is not a prime number.

\(124\) is divisble by \(2\), so it is not a prime number.

As mentioned above, \(3\) is a prime number.

Thus, only \(2\) elements are prime and we output \(2\).


There are no comments at the moment.