Дано n число, как узнать простое оно или нет в c++ ?

#include <iostream>
using namespace std;
bool is_prime(const int num) {
if (!num) return false;
bool prime;
if (num < 6 && (num <= 2 || num == 3 || num == 5)) prime = true;
else if (~num & 1 || 0 == num % 3 || 0 == num % 5) prime = false;
else {
int n;
for (n = 3; n * n <= num && num % n; n += 2) { ; }
prime = n * n > num;
}
return prime;
}
int main() {
int num;
do {
cout << "Number: ";
cin >> num;
if (is_prime(num)) cout << "Yes!\n";
else cout << "No!\n";
} while (num);
}

Простыми числами называются те целые числа, которые не делятся без остатка ни на какое другое число, кроме единицы и себя самого.

Построить решето Эратосфена от 3 до n (только для нечетных чисел), это самый быстрый способ - поскольку не используются тяжелые операции типа деления и взятия остатка. Предварительно проверив на 2, т. к - оно простое. Любое четное число не является простым. Строишь массив делителей от 3 до n включительно, заполняешь нечетными числами от исходного с шагом 2. В следующем цикле, на каждую итерацию до n зануляешь каждый j делитель (то есть шаг j), исходную позицию можно брать как квадрат j. После прохода проверяешь не попало ли 0 в последний элемент массива, если да ставишь флаг не простого числа, иначе перебираешь следующий делитель. Все описано в Вики...