Calculate the root of a number without useing the root function or decimal numbers

Question

I'm trying to build a program in c# which will calculate prime numbers for me.
I'm using the BigInteger class to work with 'endless' numbers.
However, there is a big down side on this function, I can't use decimal numbers!

My method is to calculate the root of a number, round it up, and try to divide the number with all numbers between 3 and the root of the number.
The problem is, I cannot calculate the root of a number larger then 15 digits! The method I use transforms a number like 123719028390813 into 1.23719028390813E+15. As you can guess the digits after '813' are discarded and my function now thinks the root is 2.

So I started thinking about a method to get the root (rounded up) without using a root function or decimal numbers.

So these things aren't allowed:

1. X ^ 0.5.
2. root(x).

The functions this BigInteger class supports are:

• (any)Log
• addition and subtraction
• multiply and diving
• power
• remainder
• Negative numbers

I tried a lot of things, but nothing was getting close...

So my questions:

• Is it possible to get the root of a number with conditions stated up here
• If yes, what is the way to do it???

Greetings,
Mixxiphoid

UPDATE:
I know this isn't the best or fastest method to calculate primes, I never said it should be...
I removed the prime-numbers tag, because I would also like to know whether it is a prime or not to calculate the root of a number with the tools named in my question.

Answer 1

Yes it can be done.
Suppose that you are given $n$, you want to calculate $\lceil \sqrt{n} \rceil$, so you can apply a binary search algorithm with $k^2 \geq n \land (k-1)^2 < n$ as the stopping condition. $k$ here is the variable over which you are doing the binary search. The algorithm would be like this:

low = 0
top = n
while(true)
  mid = (low+top)/2
  if(mid*mid >= n and (mid-1)*(mid-1) < n)
    return mid
  else
    if(mid*mid < n)
      low = mid + 1
    else
      top = mid-1
    end
  end
end