Monday, December 9, 2013

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

No comments:

Post a Comment