дано натуральное число, проверьте можно ли данное натуральное число вычислить произведением трех простых чисел

Question

Есть задача, не могу придумать решение, даже мысли нет, точнее как, мысли есть, сделать решето эратосфена, все числа вносить в массив, но как тогда мне нужно это все правильно перемножить? На сколько понимаю это будет 2 3 5, они перемножаются, не подходит, дальше будет 2 3 7, 2 3 11, и так до конца массива, потом будет что то в духе 3 2 5, 3 5 7, 3 5 11, потом 5 2 3, 5 3 7, 5 7 11, и т.д, но сработает ли, а если сработает то как это написать, код не прошу, просто варианты решений на словах, или если моя мысль верна, в чём я сомневаюсь, то так же вариант записи, заранее спасибо

Answer 1

Для небольших диапазонов (например, в пределах int) можно просто перебором, даже не строя таблицу простых. Просто факторизацией — разложение на простые и подсчет количества прямо по ходу разложения. Что-то вроде

bool isTriple(unsigned int N)
{
    int cnt = 0;
    while (N%2 == 0) { N/=2; cnt++;}
    if (cnt > 3) return false;
    for(int i = 3; i < sqrt(N) + 1; i+=2)
    {
        if (N%i == 0) while(N%i == 0) { N/=i; cnt++;}
        if (cnt > 3) return false;
    }
    if (N > 1) cnt++;
    return cnt == 3;
}