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.

$\endgroup$
2
  • 5
    $\begingroup$ You can find the square root using binary search. If you're lazy you can use $\sqrt{x} = \exp(\log(x)/2)$. $\endgroup$ Commented Apr 24, 2011 at 21:00
  • $\begingroup$ @Yuval Filmus could you please give some good resources to help me with that? $\endgroup$
    – Mixxiphoid
    Commented Apr 24, 2011 at 21:27

1 Answer 1

5
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ You're a genius! :). Thanks a lot, this saves me a lot of work! this method is quite fast too! $\endgroup$
    – Mixxiphoid
    Commented Apr 24, 2011 at 21:40
  • $\begingroup$ 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. $\endgroup$ Commented Apr 24, 2011 at 21:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .