Search This Blog

Friday, 14 June 2013

Prime number 3( Avoid stupid C++ behavior in case of overflow)

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

int fermatTest (int n) {
  int a, result, i;

  a = rand() % n;
  cout << "Trying with " << a << endl;
  // return (a == (int(pow(a,n)) % n)); bad way
  result = 1;
  i = n;
  while (i > 0) {
    result = (result * a) % n;
    i = i-1;
  }
  return (a == result);
}

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