Search This Blog

Friday, 14 June 2013

Prime number 2 using c++

#include <iostream.h>
#include <stdlib.h>
#include <math.h>

int fermatTest (int n) {
  int a;

  a = rand() % n;
  cout << "Trying with " << a << endl;
  return (a == (int(pow(a,n)) % n));
}

int main () {
  int n, i;
  cout << "Enter a natural number: ";
  cin >> n;
  cout << "How many trials?: ";
  cin >> i;
  srand(n*i);
  while (i > 0) {
    if (fermatTest(n)) {
      i = i-1;
    } 
    else {
      cout << "The number " << n << " is definitely not prime." << endl;
      return(0);
    }
  }
  cout << "The number " << n << " is probably prime." << endl;
  return(0);
}

No comments:

Post a Comment