Question

ІНФОРМАТИКА 8 КЛАС МОВА КОДУВАННЯ С++

Кількість майже простих


Серед N


цілих додатних чисел не більших 30000 знайти кількість майже простих чисел. Назвемо ті числа майже простими, які мають лише один дільник і той простий.



Формат вхідних даних


Кількість майже простих


У першому рядку задано ціле число N


(1≤N≤1000)


. У наступному рядку містяться цілі додатні числа не більші 10000, які розділяються пропуском.



Формат вихідних даних


У вихідний потік вивести кількість майже простих чисел.


Приклад вхідних даних


5


16 20 30 4 25


Приклад вихідних даних


2

Answer 1

#include <iostream>

#include <vector>

using namespace std;

bool is_prime(int n) {

   if (n < 2) return false;

   for (int i = 2; i * i <= n; i++) {

       if (n % i == 0) return false;

   }

   return true;

}

int count_almost_primes(int n, vector<int>& nums) {

   int count = 0;

   for (int i = 0; i < n; i++) {

       int divisors = 0;

       for (int j = 1; j <= nums[i]; j++) {

           if (nums[i] % j == 0 && is_prime(j)) {

               divisors++;

               if (divisors > 1) break;

           }

       }

       if (divisors == 1) count++;

   }

   return count;

}

int main() {

   int n;

   cin >> n;

   vector<int> nums(n);

   for (int i = 0; i < n; i++) {

       cin >> nums[i];

   }

   cout << count_almost_primes(n, nums) << endl;

   return 0;

}