This C++ program is to check whether a given number is prime or not using the above method... Try this out, you will how fast it is...

#include <iostream>

#include <time.h>

using namespace std;

int main (){

long long k, a;

again:

cin >> k;

if (k == 1){ 

cout << "Composite" << endl;

goto again;

}

if (k == 2 || k == 3){

cout << "Prime" << endl;

goto again;

}

//time

clock_t tStart = clock();

if ((k-1)%6==0){

a=(k-1)/6;

for (long long i=1; i<a/2; i++){

if ( (a-i)%(6*i+1)==0 || (a+i)%(6*i-1)==0 ){

goto out;

}

}

}else if ((k+1)%6==0){

a=(k+1)/6;

for (long long i=1; i<a/2; i++){

if ( (a-i)%(6*i-1)==0  ){

goto out;

}

}

}else{

goto out;

}

cout << "Prime" << endl;

goto skip;

out:

cout << "Composite" << endl;

skip:

//time

printf("Time taken: %.4fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

goto again;

system ("pause");

return 0;

}