2
$\begingroup$

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.

  • 0
    @Yuval Filmus could you please give some good resources to help me with that?2011-04-24

1 Answers 1

5

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 
  • 0
    You are welcome :). If you you want a faster way, I think you can adapt newthon's method to work with integers (I'm not sure about this but a few examples on paper worked). The recurrence obtained with newthon's method is: $x_n = \frac{1}{2}(x_{n-1} + \frac{n}{x_{n-1}})$. You will start with $x_0 = n$ and recalculate until $x_{n-1} = x_n$. This will actually give you $\lfloor \sqrt{n} \rfloor$ but is easy to calculate $\lceil \sqrt{n} \rceil$ from that.2011-04-24