Быстрая проверка натурального числа на простоту

int Prime(unsigned long a)
{
   unsigned long i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}

int Prime(unsigned long a)
{
   unsigned long i, j, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0)
      return 0;
   bound = sqrt((double)a);
   i = 7; j = 11;
   while (j <= bound && a%i && a%j)
   {
       i += 6; j += 6;
   }
   if (j <= bound || i <= bound && a%i == 0)
      return 0;
   return 1;
}

int Prime(unsigned long a)
{
   unsigned long i1, i2, i3, i4, i5, i6, i7, i8, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17 || a == 19 || a == 23 || a == 29)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0 || a%11 == 0 || a%13 == 0 || a%17 == 0 || a%19 == 0 || a%23 == 0 || a%29 == 0)
      return 0;
   bound = sqrt((double)a);
   i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;
   while (i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)
   {
       i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
   }
   if (i8 <= bound ||
      i1 <= bound && a % i1 == 0 ||
      i2 <= bound && a % i2 == 0 ||
      i3 <= bound && a % i3 == 0 ||
      i4 <= bound && a % i4 == 0 ||
      i5 <= bound && a % i5 == 0 ||
      i6 <= bound && a % i6 == 0 ||
      i7 <= bound && a % i7 == 0)
         return 0;
   return 1;
}

ulong d = 1 << 35;

ulong d = (ulong)1 << 35;

inline __device__ void Search(ulong a,int n, int &ret)
{
    while (n)
    {
        n >>= 1;
        if (a >> n)
        {
            ret += n;
            a >>= n;
        }
    }
}
 
__device__ void LongMod(ulong *digit, ulong count, ulong modl, int bit, ulong &ret)
{
    int how_bit = BIT;
 
    ulong digit_del = digit[0];
    ulong part = digit[1];
    ulong mod = 0;
 
    mod = digit_del % modl;
    for( ;how_bit > 0; )
    {       
        int bitLeft = 0;
        Search(mod,bit,bitLeft);
        bitLeft = BIT - bitLeft - 1;
        if(how_bit >= bitLeft)
        {
            digit_del = mod << bitLeft;
            digit_del |= (part & mask[bitLeft]) >> (BIT - bitLeft);
            part <<= bitLeft;
            how_bit -= bitLeft;
        }
        else if(how_bit > 0)
        {
            digit_del = mod << how_bit;
            digit_del |= (part & mask[how_bit]) >> (BIT - how_bit);
            how_bit = 0;
        }
        mod = digit_del % modl;
    }
    ret = mod;
}

#include <iostream>
#include <cassert>
#include <math.h>
#include <sstream>
#include <string>
#include <vector>
 
 
std::vector<int> sieve(int num)
{
    int p = 2;
    std::vector <int> s;
    for (int i = 0; i < num; i++)
    {
        s.push_back(i);
    }
    s.at(1) = 1;
 
    while (p < num)
    {
        if (s.at(p)!=0)
        {
        for (int i = p*2; i < num; i += p)
            {
                 s.at(i) = 0;
            }
        }
        p++;
    }
    return s;
}
 
int prime_factor(std::vector<int> vec, unsigned long long div)
{
    int prime = 0;
    for (int i = 0; i < std::sqrtl(div) - 1; i++)
    {
        if (vec.at(i) == 0) {continue;}
        if (div % vec.at(i) == 0)
        {
            prime = vec.at(i);
        }
        i++;
    }
    return prime;
}
 
int solve(unsigned long long num)
{
    std::vector<int> array; 
    int prime;
    int count = std::sqrtl(num);
    array = sieve(count);
    prime = prime_factor(array, num);
    return prime;
}
 
void main(int argc, char *argv[])
{
    unsigned long long arg = 1;
    if (argc >= 1)
    {
        std::stringstream ss;
        ss << argv[1];
        ss >> arg;
    }
    std::cout << solve(arg) << std::endl;
 
}

if (x == a1 || x == a2 || ...)
   return false;
int sqrt = sqrt_int(x);
int step = std::accumulate(...) //тут получаем произведение всех этих простых чисел. Хотя тут уже double наверное нужно юзать, в int вряд ли влезет
for(int i = 0; i < sqrt; i+=)
   if (x%i == 0)
      return false;
return true;

if(n%6==1 || n%6==5)
Проверять его
else return не простое