Fast Prime Number

prime.cpp

#include <iostream>


/*
 * function is_prime(n)
    if n ≤ 3 then
        return n > 1
    else if n mod 2 = 0 or n mod 3 = 0
        return false

    let i ← 5

    while i × i ≤ n do
        if n mod i = 0 or n mod (i + 2) = 0
            return false
        i ← i + 6

    return true
*/

bool is_prime(long long int n) {
    if (n <= 3) return n > 1;
    else if (n % 2 == 0 || n % 3 == 0) return false;
    int i = 5;
    while (i * i <= n) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
        i += 6;
    }
    return true;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int size= 0;
    std::cin >> size;
    for (int i = 0; i < size; ++i) {
        long long int value = 0;
        std::cin >> value;
        if (is_prime(value)) std::cout << "Prime\n";
        else std::cout << "Not Prime\n";
    }
    return 0;
}