How to find the number of prime numbers in an array?

Question

Algorithms

It is necessary to implement an algorithm that will count the number of primes in the given array. Memory limit 256 MB, time 1 second.
Input Format

• The first line contains a single number 1 ≤ n ≤ 1000 - the sample size
  
• The second line contains n integers 2 ≤ a _i ≤ 10 ¹² - sample
  

Sample Input 3:
5
15 17 2 8 15
Sample Output 3:
2

The problem is in the upper limit of the possible number in the sample, when it really approaches 12 zeros, exceptions of the MemoryError type occur, and if this problem is also solved, then the algorithm does not fit into the required 1 give me a sec.
I tried to use the sieve of Eratosthenes in various implementations, but nothing came of it. I suspect that it is possible to solve with the help of generators, but my skills are not enough yet.

Answer 1

There is no need for a sieve. You just need to separately check each number for simplicity.
Hint: If the number is not prime, then it has a prime divisor not greater than the root (because otherwise there are at least 2 divisors and they are both greater than the root and their product is already greater than the number itself).

Answer 2

It's not clear where you get the MemoryError. If the original sample is in memory, and there is enough space for it, then what is your memory spent on? You don't have to memorize all the prime numbers you get. You take them one at a time and just find out if it's simple or not.
Over time - yes, if you have really large numbers and there are also a lot of them - well, then the enumeration algorithm will not be fast. So the 1 second limit. - it's just some kind of strangeness, to put it mildly, if you do not specify which numbers in your sequence. For 1000 numbers, all in the range from 0 to 1001 - this is one thing, and for those in the range from 10**12-1000 to 10**12 - this is a completely different operating time.

Answer 3

The task clearly requires the calculation of these very prime numbers and the reuse of the list.
So first we generate a list of prime numbers in a sane range, say, up to a thousand. Let's take another number. If it is less than the square of the largest of the primes in the list, check that it is divisible or not divisible by one of them. And if there are more, just before checking, we will add prime numbers to the list up to the desired threshold. In this case, we use again the same procedure for checking a number for simplicity.
No, of course, you can immediately generate up to a million simple ones, but what's the point?