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

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;
}

//------------Простое ли число?----------------------
bool isPrime(int number)
{
char buffer [50]="";
sprintf (buffer, "%d", number);
if (buffer [0] == '-')
return false;
if ( number == 0 || number == 1) return false;
int divisor;
for (divisor = number / 2; number%divisor != 0; --divisor);
return divisor == 1;
}

int main()
{
    const int N=50001;//Задаем размер выборки
    int arr[N];//Инициализируем массив для чисел 2 до N
    int k=0;
    int i;
    int bigResArr[N];//Результирующий массив для чисел больше 10
    int smallResArr[6];//Резальтирующий массив для чисел меньше 10
 
    //Цикл заполнения массива числами от 2 до N
    for(i=2; i<N; ++i){
        arr[k]=i;
        k++;
    }
 
    //Цикл для выполнения поиска и записавания простых чисел. Все операции привязаны к переменной k(номер элемента массивов)
    for(k=0; k<N; ++k)
    {
        if(arr[k]!=1 || arr[k]!=4 || arr[k]!=6 || arr[k]!=8 || arr[k]!=9)
        {
            //Условие заполнения результирующего массива простыми числами меньше 10
            if(arr[k]==2|| arr[k]==3 || arr[k]==5 || arr[k]==7)
            {
                smallResArr[k]=arr[k];
            }
            else
                {
            //Условие заполнения результирующего массива простыми числами большими чем 10
            if(arr[k]%2==0 || arr[k]%3==0 || arr[k]%5==0 || arr[k]%7==0)
                    {
                
                    }
            else
                        {
            bigResArr[k]= arr[k];
                        }       
                }
        }
    }
return 0;
}

#include <iostream>
 
int main()
{
   int x = 10;
   std::cin >> x;
   std::cout << ((x&1)?"prostoe, sto pudov":"ne prostoe") << std::endl;
}

//программа поиска простых чисел методом перебора делителей
#include<iostream>
#include <ctime>
using namespace std;
 
 
int main() 
{
    long max =1000000;//диапазон поиска от 1 до мах
    int n(0);//счетчик найденных простых чисел
    int s;
    clock_t timer;
    timer = clock();//время начала поиска
    cout << "Simple numbers: 0>>>"<<max<<endl;
    
    for ( int i = 1; i < max; i+=2)//проверяем все нечетные числа
    {
        s=0;//обнуляем счетчик делителей
        for (int j = 3; j <= i/j; j++) {
            //находим остаток от деления числа i на j 
            if (i % j == 0) {
                s++;//если остаток от деления равно 0, то j является делителем числа i, увеличиваем счетчик делителей на 1
                break;//проверяем следующее число
            }
        }
        if (s == 0) {  n++; }//простое число равно значению i при желании можно распечатать на экран, но снижает скорость
        
    }
    timer = clock()-timer ;//вычисляем время потраченное на поиск
    cout << "\n\aend:" << float(timer)/CLOCKS_PER_SEC<<"s"<<endl;
    cout << "find " << n << " numbers.\n";
    system("pause");
    return 0;
}

int k;
    vector<int> Array;               //Создаем переменную для числа и Вектор с последовательностью Люка
    
    
    while(true)                      //Бесконечный цикл
    {
    
    system("cls");
    cout << "Enter your number: ";
    cin >> k;
    Array.reserve(k);
    Array[0] = 2;
    Array[1] = 1;                              //Запрос данных, а так же подготовка Вектора
    
    for(int i = 0; i < k - 1; i++)                          //Генерим последовательность до нужного числа
    {
        Array[i + 2] = Array[i + 1] + Array[i];
    }
    
    
    if((Array[k] - 1) % k == 0)                                                //Проверка по формуле
    {
        cout <<"\n\n"<< k <<" is Simple  (1)...\n";
        //cout << "\n\n\nOSU: " << (Array[k] - 1) % k << "\n\n";
       //cout << "\n\n\n(" << Array[k - 1] << " - 1) / " << k << "\n\n";          В комменте отладочная информация
        cout << "\n\n\n\n\nInput Any Key and Press Enter\n\n"; 
        cin >> k;
    }
    
    
    
    else
    {
        cout <<"\n\n"<< k <<" is not Simple (0)...\n"; 
      //    cout << "\n\n\n(" << Array[k - 1] << " - 1) / " << k << "\n\n";
        cout << "\n\n\n\n\nInput Any Key and Press Enter\n\n";
        cin >> k;
    }
    
    
    }

for (j=2; j<=(i/j); j++)
if (!(i%j)) break;
if (j > (i/j)) cout << i << " - simple number\n";
}
return 0;
}