Computer Science Canada

Larger Integers
Author:  drij [ Sun Oct 12, 2008 2:18 pm ]
Post subject:  Larger Integers
I was working my way through the problems on Project Euler when I encountered an issue with problem 3.

The problem is: "What is the largest prime factor of 600851475143?"

I wrote a nice little prime-checking function:
Turing:
fcn isPrime (maybePrime : int) : boolean
    var hasNoFactors : boolean := true

    if maybePrime = 1 or maybePrime = 2 then
        result true
    end if

    for maybeFactor : 2 .. floor (sqrt (maybePrime))
        if maybePrime mod maybeFactor = 0 then
            hasNoFactors := false
        end if
    end for

    result hasNoFactors
end isPrime

After I wrote this, I couldn't figure out how to deal with the size of the number 600851475143.

My question is, is it possible to work with large numbers such as this in turing?
Author:  OneOffDriveByPoster [ Sun Oct 12, 2008 4:52 pm ]
Post subject:  Re: Larger Integers
Yes, the double-precision floating point can represent at least this, and all the integers >= 0 below it exactly.
Author:  Saad [ Sun Oct 12, 2008 4:58 pm ]
Post subject:  RE:Larger Integers
But it should be known that it can not represent accurately be represented. Unfortunately Turing has no default way of handling them with full accuray. You could make your own though.
Author:  Insectoid [ Sun Oct 12, 2008 9:02 pm ]
Post subject:  RE:Larger Integers
does Turing not support 'long' variables?
Author:  Saad [ Sun Oct 12, 2008 9:46 pm ]
Post subject:  RE:Larger Integers
None to my knowledge
Author:  [Gandalf] [ Sun Oct 12, 2008 9:48 pm ]
Post subject:  RE:Larger Integers
Nope, it doesn't. float is as much precision as you can get.
Author:  drij [ Mon Oct 13, 2008 10:27 am ]
Post subject:  Re: Larger Integers
Ok then. Thanks for all your replies. Smile
Author:  [Gandalf] [ Mon Oct 13, 2008 7:20 pm ]
Post subject:  RE:Larger Integers
If you're looking to get further ahead in Euler, and are willing to learn a new language that's not too difficult, I'd recommend Ruby or Python. Both, AFAIK, support arbitrarily long integers by default.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy