-1

If computers used base 6 (senary), they could easily find if N is divisible by 2 or 3, and thanks to the digits-sum rules (omega and alpha totatives) they could also easily figure out if N is divisible by 5 or 7.

But computers use base 2 (binary). So they can easily figure out if N is divisble by 2, and thanks to the digit-sum rule (alpha totative) they can also figure out if N is divisible by 3.

To find out if N is divisible by 5, they could convert N to base 16 (hexadecimal), and use the digit-sum rule (omega totative) to find if N is divisible by 5.

I don't know... are there other methods?

user50746
  • 281
  • 2
  • 4
  • 10
  • 2
    Well, you can do regular long division and check the remainder. – Hot Licks Oct 14 '14 at 01:10
  • 1
    Believe it or not, computers can do division by numbers other than two. – Jonathon Reinhart Oct 14 '14 at 01:13
  • `10**10` (11 digits) is not a big number. The largest known prime (the number that we know is only divisible by 1 and iself) has more than 10 millions of digits. – jfs Oct 14 '14 at 01:17
  • for small numbers such as `10**10` see [The integer division algorithm of x86 processors](http://stackoverflow.com/q/8401194/4279) – jfs Oct 14 '14 at 01:28
  • for larger numbers, see [what division algorithms GNU MP library uses](https://gmplib.org/manual/Division-Algorithms.html#Division-Algorithms) – jfs Oct 14 '14 at 01:36

1 Answers1

0

It will solve this the way it solves any other 64 bit integer.

log2 10^10 ~= 33.219

This means this number and lots of other numbers are representable by a 64bit int.

You can just test 

std::vector<int64_t> primes = {2,3,5,7,11,13,17,19,23,29}; 
int64_t  mynumber = 0x2540BE400;

for (int64_t prime : primes)
{
    if (mynumber % prime == 0)
    {
        std::cout << mynumber << " is divisible by " << prime << std::endl;
    }
}

For details on the implementation of % and / the following paper is a good reference: http://www.diva-portal.org/smash/get/diva2:347845/FULLTEXT01.pdf

Jon
  • 1,785
  • 2
  • 19
  • 33