Finding First 10 Digit Prime Number in The Value Of Pi

List<string> numbersChecked;

// Calculation starts when user clicks on the button on UI
private void btnFindPrime_Click(object sender, EventArgs e)
{
  //a collection to store the numbers that are checked for being prime.
  numbersChecked = new List<string>();

  //Calculate the value of PI (actually returns a constant string up to 100000 digits of pi)
  string Pi = CalculatePI();

  StringBuilder sb = new StringBuilder();
  //start from first digit of pi to the last but 10th digit
  for (int i = 0; i < Pi.Length - 10; i++)
  {
    sb = new StringBuilder();

    //take 10 digits from pi, starting at i index.
    for (int j = 0; j < 10; j++)
      sb.Append(Pi[i + j]);
 
    //convert from string builder to string, to prevent conversion at 4 other places below.
    string str = sb.ToString();
 
    //if this number is already checked for prime-ness, continue to next number
    if (numbersChecked.Contains(str))
      continue;
 
    //Check if the number is prime, if so, display it and break the loop
    if (IsPrime(str))
    {
      txt.Text += str;
      break;
    }

    //add this number to the list of checked numbers
    numbersChecked.Add(str);
  }
}

// This method returns the value of pi to 100000th digits after decimal place,
// initially i calculated value of pi to 10000 digit by dividing 22 by 7
// (ok, i am not from maths so didn't knew 22/7 is just an approximation)
//
// The value of pi up to 100000 digits is taken from http://wiki.answers.com/Q/What_is_the_exact_value_of_pi
//
// The return value do not contain decimal point to ease the loop done above
//
//Note: for posting reduced the value of pi to 20 digits;
private string CalculatePI()
{
  return "314159265358979323846";
}

// checks if a number is prime or not
// as per the problem, it was required to calculate for 10 digit number,
// so if lenght is greater than 10 digits, an exception is thrown (ok, i am throwing System.Exception)
//
// if the number is prime, it returns true, otherwise false
private bool IsPrime(string str)
{ 
  // if the number of digits in the number is more than 10, throw the exception 
  if (str.Length > 10) 
    throw new Exception("error in code"); 
  
  //if the number is greater than two digits, then check for last digit
  if (str.Length >= 2)
    // if the number ends in 0, 2, 4, 5, 6, or 8, it is not prime
    if (str.EndsWith("0") || str.EndsWith("2") || str.EndsWith("4") || str.EndsWith("5") || str.EndsWith("6") || str.EndsWith("8"))
      return false; 
  
  // convert the number to long (fortunately long in C# can hold up to 8 byte (64bit) values, so no problem
  long number = long.Parse(str);
 
  // Just updating the user interface to be sure that the application is working
  this.Text = "Calculating for " + str;
  Application.DoEvents();
 
  // calculate from the square root of the number down to 2 (1 excluded),
  // if the number is fully divisible by a fraction, it is not prime, so return false
  for (long fraction = (long)Math.Sqrt(number); fraction > 1; fraction--)
    if (number % fraction == 0)
      return false;
 
  // if the number is not divisible by any fraction, it is prime; so return true
  return true;
}

2 Comments.....

Rajat 12/25/2010 9:18:14 AM I suggest a little modification in the IsPrime method. private bool IsPrime(string str) { // if the number of digits in the number is more than 10, throw the exception if (str.Length > 10) throw new Exception("error in code"); //if the number is greater than two digits, then check for last digit if (str.Length >= 2) // if the number ends in 0, 2, 4, 5, 6, or 8, it is not prime if (str.EndsWith("0") || str.EndsWith("2") || str.EndsWith("4") || str.EndsWith("5") || str.EndsWith("6") || str.EndsWith("8")) return false; // rest of the code } I understand the fact that there is no need of throwing an exception if the string passed is not prime even if the length of the string is more than 10 digits. But if we are not allowing any string of more than 10 digits then its logical to throw an exception without bothering the type of string (i.e prime or not). Plz correct me if I am wrong.

Manish Dalal 12/26/2010 10:42:25 AM Very true Rajat, the exception should be thrown if the length is greater than ten. The test for prime should be done only if the length is less than 10 digits. I will update the code to reflect your suggestion.

Post Comment

Name:  
Email:  
You will receive an email to approve your comment.

Comment: